Scale Engineer

Sliding Subarray Beauty

Med
#2410Time: O(n * k log k) The outer loop runs `n - k + 1` times. In each iteration, we iterate `k` times to form a list of negative numbers. The size of this list can be up to `k`. Sorting this list takes `O(k log k)` time. Thus, the total time complexity is `O((n - k + 1) * k log k)`.Space: O(n) We use `O(k)` extra space for the list of negative numbers in each iteration. The result array requires `O(n - k + 1)` space, making the total `O(n)`.
Patterns
Sliding Window
Data structures
ArrayHash Table

Prompt

Given an integer array nums containing n integers, find the beauty of each subarray of size k.

The beauty of a subarray is the xth smallest integer in the subarray if it is negative, or 0 if there are fewer than x negative integers.

Return an integer array containing n - k + 1 integers, which denote the beauty of the subarrays in order from the first index in the array.

  • A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

[1, -1, -3]

Example 2:

[-1, -2]

Example 3:

[-3, 1]

 

Constraints:

  • n == nums.length 
  • 1 <= n <= 105
  • 1 <= k <= n
  • 1 <= x <= k 
  • -50 <= nums[i] <= 50 

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every possible subarray of size k. For each subarray, it identifies all the negative numbers, sorts them, and then finds the x-th smallest one to determine the beauty.

Algorithm

  • Initialize an empty result array ans.
  • Iterate with a start index i from 0 to n - k.
  • For each i, create a new list negatives.
  • Iterate from j = i to i + k - 1 to form the subarray.
  • If nums[j] is negative, add it to the negatives list.
  • If negatives.size() < x, the beauty is 0.
  • Otherwise, sort the negatives list and the beauty is the element at index x - 1.
  • Add the beauty to the ans array.
  • Return ans.

Walkthrough

The algorithm proceeds as follows:

  1. We initialize an answer array ans of size n - k + 1 to store the beauty of each subarray.
  2. We loop from the first possible starting index i = 0 up to n - k. Each i represents the beginning of a new subarray.
  3. For each subarray starting at i and of length k (i.e., nums[i...i+k-1]), we create a temporary list.
  4. We iterate through this subarray and add all negative numbers to our temporary list.
  5. After collecting all negative numbers, we sort this list in ascending order.
  6. We then check the size of the list. If the number of negative elements is less than x, the beauty is defined as 0.
  7. If there are x or more negative numbers, the x-th smallest negative number is at index x-1 in the sorted list. This value is the beauty.
  8. We store the calculated beauty in the ans array at the corresponding index.
  9. After iterating through all possible subarrays, we return the ans array.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    public int[] getSubarrayBeauty(int[] nums, int k, int x) {        int n = nums.length;        int[] result = new int[n - k + 1];                for (int i = 0; i <= n - k; i++) {            // For each subarray, collect negative numbers            List<Integer> negatives = new ArrayList<>();            for (int j = i; j < i + k; j++) {                if (nums[j] < 0) {                    negatives.add(nums[j]);                }            }                        // If there are fewer than x negative numbers, beauty is 0            if (negatives.size() < x) {                result[i] = 0;            } else {                // Otherwise, sort and find the x-th smallest                Collections.sort(negatives);                result[i] = negatives.get(x - 1);            }        }                return result;    }}

Complexity

Time

O(n * k log k) The outer loop runs `n - k + 1` times. In each iteration, we iterate `k` times to form a list of negative numbers. The size of this list can be up to `k`. Sorting this list takes `O(k log k)` time. Thus, the total time complexity is `O((n - k + 1) * k log k)`.

Space

O(n) We use `O(k)` extra space for the list of negative numbers in each iteration. The result array requires `O(n - k + 1)` space, making the total `O(n)`.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem for smaller inputs.

Cons

  • Inefficient due to re-computation for each subarray.

  • Sorting within the loop makes it slow, especially for large k.

  • Does not pass for the given constraints and will likely result in a 'Time Limit Exceeded' error.

Solutions

class Solution {public  int[] getSubarrayBeauty(int[] nums, int k, int x) {    int n = nums.length;    int[] cnt = new int[101];    for (int i = 0; i < k; ++i) {      ++cnt[nums[i] + 50];    }    int[] ans = new int[n - k + 1];    ans[0] = f(cnt, x);    for (int i = k, j = 1; i < n; ++i) {      ++cnt[nums[i] + 50];      --cnt[nums[i - k] + 50];      ans[j++] = f(cnt, x);    }    return ans;  }private  int f(int[] cnt, int x) {    int s = 0;    for (int i = 0; i < 50; ++i) {      s += cnt[i];      if (s >= x) {        return i - 50;      }    }    return 0;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem