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

Array Hash 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 x^th 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 <= 10⁵
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:

We initialize an answer array ans of size n - k + 1 to store the beauty of each subarray.
We loop from the first possible starting index i = 0 up to n - k. Each i represents the beginning of a new subarray.
For each subarray starting at i and of length k (i.e., nums[i...i+k-1]), we create a temporary list.
We iterate through this subarray and add all negative numbers to our temporary list.
After collecting all negative numbers, we sort this list in ascending order.
We then check the size of the list. If the number of negative elements is less than x, the beauty is defined as 0.
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.
We store the calculated beauty in the ans array at the corresponding index.
After iterating through all possible subarrays, we return the ans array.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public int[] getSubarrayBeauty(int[] nums, int k, int x) {7        int n = nums.length;8        int[] result = new int[n - k + 1];9        10        for (int i = 0; i <= n - k; i++) {11            // For each subarray, collect negative numbers12            List<Integer> negatives = new ArrayList<>();13            for (int j = i; j < i + k; j++) {14                if (nums[j] < 0) {15                    negatives.add(nums[j]);16                }17            }18            19            // If there are fewer than x negative numbers, beauty is 020            if (negatives.size() < x) {21                result[i] = 0;22            } else {23                // Otherwise, sort and find the x-th smallest24                Collections.sort(negatives);25                result[i] = negatives.get(x - 1);26            }27        }28        29        return result;30    }31}

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.

This approach uses the sliding window technique combined with a frequency map to efficiently calculate the beauty of each subarray. The key observation is that the range of numbers is small (-50 to 50), which allows us to use a frequency array (acting as a form of counting sort) to track the counts of negative numbers in the current window. This avoids the costly sorting step in each iteration.

Algorithm

Create a frequency array freq of size 51 to store counts of negative numbers from -1 to -50.
Initialize the first window: iterate from i = 0 to k-1, and if nums[i] is negative, increment freq[-nums[i]].
Calculate the beauty for the first window by calling a helper function findXthSmallest and store it in the result.
The findXthSmallest function iterates from i = 50 down to 1 (representing numbers -50 to -1). It accumulates the frequencies. When the accumulated count is >= x, it returns -i. If the loop completes, it means there are fewer than x negative numbers, so it returns 0.
Slide the window from i = k to n-1:
- Decrement the frequency of the element leaving the window, nums[i-k], if it's negative.
- Increment the frequency of the element entering the window, nums[i], if it's negative.
- Calculate the beauty for the new window using findXthSmallest and store it.
Return the result array.

Walkthrough

The algorithm works by maintaining a count of each negative number within the current window of size k.

We use a frequency array, freq, of size 51. We can map each negative number num to an index in this array. A convenient mapping is to use freq[-num] to store the count of num. For example, the count of -1 is stored at freq[1], -2 at freq[2], and so on, up to -50 at freq[50].
First, we process the initial window of k elements (nums[0...k-1]). We iterate through these elements and update the freq array for any negative numbers encountered.
After populating the frequency map for the first window, we find its beauty. To do this, we iterate through our possible negative numbers from smallest to largest (i.e., from -50 to -1). This corresponds to iterating through our freq array from index 50 down to 1. We accumulate the counts until the total count is at least x. The number corresponding to the index where this happens is the x-th smallest negative number. If we go through all negative numbers and the total count is less than x, the beauty is 0.
We store this first beauty value in our result array.
Then, we slide the window one position at a time from left to right. For each step, we update the freq array:
- Decrement the count for the element that is leaving the window (if it's negative).
- Increment the count for the element that is entering the window (if it's negative).
After each slide, the freq array accurately reflects the counts of negative numbers in the new window. We then repeat the process of finding the beauty using the updated freq array and store it in our result.
This continues until the window has traversed the entire array.

1class Solution {2    public int[] getSubarrayBeauty(int[] nums, int k, int x) {3        int n = nums.length;4        int[] result = new int[n - k + 1];5        // freq[i] will store the count of number -i.6        // We only care about negative numbers from -1 to -50.7        int[] freq = new int[51]; 8 9        // Initialize the first window10        for (int i = 0; i < k; i++) {11            if (nums[i] < 0) {12                freq[-nums[i]]++;13            }14        }15 16        result[0] = findXthSmallest(freq, x);17 18        // Slide the window19        for (int i = k; i < n; i++) {20            // Add the new element21            if (nums[i] < 0) {22                freq[-nums[i]]++;23            }24            // Remove the old element25            if (nums[i - k] < 0) {26                freq[-nums[i - k]]--;27            }28            29            result[i - k + 1] = findXthSmallest(freq, x);30        }31 32        return result;33    }34 35    private int findXthSmallest(int[] freq, int x) {36        int count = 0;37        // Iterate from -50 to -1 to find the x-th smallest38        for (int i = 50; i >= 1; i--) {39            count += freq[i];40            if (count >= x) {41                return -i;42            }43        }44        // If fewer than x negative numbers exist45        return 0;46    }47}

Complexity

Time

O(n) Initializing the first window takes `O(k)`. The main loop runs `n - k` times. Inside the loop, updating the frequency array takes `O(1)`. The `findXthSmallest` function takes a constant amount of time, `O(C)` where C=50, as it iterates up to 50 times. Therefore, the total time complexity is `O(k + (n - k) * C)`, which simplifies to `O(n)` as C is a small constant.

Space

O(n) The result array requires `O(n - k + 1)` space. The frequency array requires `O(C)` space, where `C` is the range of negative numbers (50). Since `C` is a constant, the total space complexity is dominated by the result array, making it `O(n)`.

Trade-offs

Pros

Highly efficient, with linear time complexity.
Effectively uses the constraint on the range of input values.
Optimal solution for this problem.

Cons

The logic is slightly more complex than the brute-force approach.
This approach is only efficient because the range of values is small and fixed. It would not be suitable if the numbers could be arbitrarily large.

Solutions

Solution

1class Solution {2public3  int[] getSubarrayBeauty(int[] nums, int k, int x) {4    int n = nums.length;5    int[] cnt = new int[101];6    for (int i = 0; i < k; ++i) {7      ++cnt[nums[i] + 50];8    }9    int[] ans = new int[n - k + 1];10    ans[0] = f(cnt, x);11    for (int i = k, j = 1; i < n; ++i) {12      ++cnt[nums[i] + 50];13      --cnt[nums[i - k] + 50];14      ans[j++] = f(cnt, x);15    }16    return ans;17  }18private19  int f(int[] cnt, int x) {20    int s = 0;21    for (int i = 0; i < 50; ++i) {22      s += cnt[i];23      if (s >= x) {24        return i - 50;25      }26    }27    return 0;28  }29}

1class Solution {2public:3  vector<int> getSubarrayBeauty(vector<int> &nums, int k, int x) {4    int n = nums.size();5    int cnt[101]{};6    for (int i = 0; i < k; ++i) {7      ++cnt[nums[i] + 50];8    }9    vector<int> ans(n - k + 1);10    auto f = [&](int x) {11      int s = 0;12      for (int i = 0; i < 50; ++i) {13        s += cnt[i];14        if (s >= x) {15          return i - 50;16        }17      }18      return 0;19    };20    ans[0] = f(x);21    for (int i = k, j = 1; i < n; ++i) {22      ++cnt[nums[i] + 50];23      --cnt[nums[i - k] + 50];24      ans[j++] = f(x);25    }26    return ans;27  }28};

1from sortedcontainers import SortedList class Solution : def getSubarrayBeauty ( self , nums : List [ int ], k : int , x : int ) -> List [ int ]: sl = SortedList ( nums [: k ]) ans = [ sl [ x - 1 ] if sl [ x - 1 ] < 0 else 0 ] for i in range ( k , len ( nums )): sl . remove ( nums [ i - k ]) sl . add ( nums [ i ]) ans . append ( sl [ x - 1 ] if sl [ x - 1 ] < 0 else 0 ) return ans

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 problem