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:
Input: nums = [1,-1,-3,-2,3], k = 3, x = 2 Output: [-1,-2,-2] Explanation: There are 3 subarrays with size k = 3. The first subarray is[1, -1, -3]and the 2nd smallest negative integer is -1. The second subarray is[-1, -3, -2]and the 2nd smallest negative integer is -2. The third subarray is[-3, -2, 3]and the 2nd smallest negative integer is -2.
Example 2:
Input: nums = [-1,-2,-3,-4,-5], k = 2, x = 2 Output: [-1,-2,-3,-4] Explanation: There are 4 subarrays with size k = 2. For[-1, -2], the 2nd smallest negative integer is -1. For[-2, -3], the 2nd smallest negative integer is -2. For[-3, -4], the 2nd smallest negative integer is -3. For[-4, -5], the 2nd smallest negative integer is -4.
Example 3:
Input: nums = [-3,1,2,-3,0,-3], k = 2, x = 1 Output: [-3,0,-3,-3,-3] Explanation: There are 5 subarrays with size k = 2. For[-3, 1], the 1st smallest negative integer is -3. For[1, 2], there is no negative integer so the beauty is 0. For[2, -3], the 1st smallest negative integer is -3. For[-3, 0], the 1st smallest negative integer is -3. For[0, -3], the 1st smallest negative integer is -3.
Constraints:
n == nums.length 1 <= n <= 1051 <= k <= n1 <= x <= k -50 <= nums[i] <= 50 Problem Overview: Given an integer array nums, a window size k, and an integer x, evaluate every contiguous subarray of length k. The “beauty” of a window is the x-th smallest negative number inside it. If the window contains fewer than x negative values, the beauty is 0. The task is to compute this value for every sliding window across the array.
Approach 1: Brute Force with Sorting (O(n * k log k) time, O(k) space)
For each starting index, copy the next k elements to form the current window. Filter or scan for negative numbers, sort them, and pick the x-th smallest negative value. If the window has fewer than x negatives, return 0. This approach directly follows the problem definition and is useful for verifying correctness. The downside is performance: sorting up to k elements for every window results in O(n * k log k) time, which becomes slow for large inputs.
Approach 2: Sliding Window with Multisets (O(n log k) time, O(k) space)
The optimized approach maintains a dynamic view of the current window using a sliding window technique from Sliding Window. Instead of rebuilding the window each time, insert the incoming element and remove the outgoing element as the window shifts. A multiset (or balanced ordered structure) keeps window elements sorted automatically. This allows efficient insertion and deletion in O(log k) time.
To compute the beauty, focus only on negative numbers. Iterate through the ordered structure (or maintain a subset of negatives) and retrieve the x-th smallest negative element. If fewer than x negatives exist, return 0. Because each element is inserted and removed once, the total complexity becomes O(n log k). This method combines ordered storage with incremental updates and fits naturally with array processing problems involving arrays and frequency tracking techniques similar to hash tables.
Recommended for interviews: Start by explaining the brute force solution to demonstrate understanding of the definition of window beauty. Then move to the sliding window with multiset optimization. Interviewers expect you to avoid recomputing the entire window each time and instead maintain state as the window moves. The optimized approach shows strong knowledge of sliding window patterns and ordered data structures.
This approach involves generating each subarray of size k, extracting negative numbers from each subarray, sorting them, and then selecting the xth smallest negative number.
For each subarray, this requires O(k log k) time for sorting, and since there are n-k+1 such subarrays, the entire approach runs in O((n-k+1) * k log k) time.
This implementation iterates through each subarray of size k, extracts negative numbers, sorts them, and picks the xth smallest negative number. If there are insufficient negatives, it appends 0.
Python
JavaScript
Java
Time Complexity: O((n-k+1) * k log k)
Space Complexity: O(k), for storing subarray negatives.
This improved approach leverages multiset-like data structures to manage the sliding window of negative numbers efficiently. The sliding window mechanism allows us only to consider the changes needed as we slide across the array.
By keeping a sorted list of negative numbers in the current window, we can find the xth smallest negative quickly without sorting. This minimizes redundant work and improves efficiency.
This approach uses SortedList from the sortedcontainers module to dynamically maintain a sorted list of negatives in the current window. It ensures efficient insertions and deletions, making it suitable for sliding window problems.
Python
JavaScript
C++
Time Complexity: O(n log k)
Space Complexity: O(k), due to the space needed for storing negatives.
We notice that the range of elements in the array nums is [-50,50]. Therefore, we can use an array of length 101, denoted as cnt, to count the occurrences of each number in [-50,50]. Due to the presence of negative numbers, we can add 50 to each number to make them all non-negative, so we can use the array cnt to count the occurrences of each number.
Next, we traverse the array nums, maintaining a sliding window of length k. The occurrence times of all elements in the window are recorded in the array cnt. Then we traverse the array cnt to find the x-th smallest number, which is the beauty value of the current sliding window. If there is no x-th smallest number, then the beauty value is 0.
The time complexity is O(n times 50), and the space complexity is O(100). Where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
We can use two priority queues (min-max heap) to maintain the elements in the current window, one priority queue stores the smaller x elements in the current window, and the other priority queue stores the larger k - x elements in the current window. We also need a delayed deletion dictionary delayed to record whether the elements in the current window need to be deleted.
We design a class MedianFinder to maintain the elements in the current window. This class includes the following methods:
add_num(num): Add num to the current window.find(): Return the beauty value of the current window.remove_num(num): Remove num from the current window.prune(pq): If the top element of the heap is in the delayed deletion dictionary delayed, pop it from the top of the heap and subtract one from its delayed deletion count. If the delayed deletion count of the element is zero, delete it from the delayed deletion dictionary.rebalance(): Balance the size of the two priority queues.In the add_num(num) method, we first consider adding num to the smaller queue. If the count is greater than x or num is less than or equal to the top element of the smaller queue, add num to the smaller queue; otherwise, add num to the larger queue. Then we call the rebalance() method to ensure that the number of elements in the smaller queue does not exceed x.
In the remove_num(num) method, we increase the delayed deletion count of num by one. Then we compare num with the top element of the smaller queue. If num is less than or equal to the top element of the smaller queue, update the size of the smaller queue and call the prune() method to ensure that the top element of the smaller queue is not in the delayed deletion dictionary. Otherwise, we update the size of the larger queue and call the prune() method to ensure that the top element of the larger queue is not in the delayed deletion dictionary.
In the find() method, if the size of the smaller queue is equal to x, return the top element of the smaller queue, otherwise return 0.
In the prune(pq) method, if the top element of the heap is in the delayed deletion dictionary, pop it from the top of the heap and subtract one from its delayed deletion count. If the delayed deletion count of the element is zero, delete it from the delayed deletion dictionary.
In the rebalance() method, if the size of the smaller queue is greater than x, add the top element of the smaller queue to the larger queue and call the prune() method to ensure that the top element of the smaller queue is not in the delayed deletion dictionary. If the size of the smaller queue is less than x and the size of the larger queue is greater than 0, add the top element of the larger queue to the smaller queue and call the prune() method to ensure that the top element of the larger queue is not in the delayed deletion dictionary.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array nums.
Similar problems:
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O((n-k+1) * k log k) |
| Optimized Sliding Window with Multisets | Time Complexity: O(n log k) |
| Sliding Window | — |
| Double Priority Queue (Min-Max Heap) + Delayed Deletion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Sorting | O(n * k log k) | O(k) | Useful for small inputs or validating logic before optimizing |
| Sliding Window with Multiset | O(n log k) | O(k) | General case for large arrays where windows shift frequently |
Leetcode Weekly contest 342 - Medium - Sliding Subarray Beauty • Prakhar Agrawal • 2,871 views views
Watch 9 more video solutions →Practice Sliding Subarray Beauty with our built-in code editor and test cases.
Practice on FleetCode