#2653

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Sliding Subarray Beauty

Compute the xth smallest negative number in each sliding subarray using array scanning and hash frequency tracking efficiently.

array hash table sliding window

Problem Statement

Given an integer array nums of length n, calculate the beauty of each subarray of size k. The beauty is defined as the xth smallest negative integer in the subarray or 0 if fewer than x negative numbers exist.

Return an array of length n - k + 1 containing the beauty values in the order of the subarrays starting from index 0. Apply array scanning combined with hash table tracking to efficiently determine each window's negative frequency.

Examples

Example 1

Input: nums = [1,-1,-3,-2,3], k = 3, x = 2

Output: [-1,-2,-2]

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]

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]

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 <= 105
1 <= k <= n
1 <= x <= k
-50 <= nums[i] <= 50

Solution Approach

Frequency Map for Negatives

Initialize a hash map to count negative numbers in the first window. Update this map as the window slides, removing counts for elements leaving and adding for elements entering. This lets you quickly determine the xth smallest negative.

Sliding Window Mechanics

Use two pointers to represent the window's start and end. As you move the window, update the negative frequency map. After each shift, scan the sorted negative counts to extract the xth smallest negative or return 0 if there are fewer than x negatives.

Optimized Lookup

Since nums[i] is bounded between -50 and 50, maintain a fixed-size array for negative counts instead of a dynamic map. This reduces overhead and allows O(1) updates per element, keeping the overall time manageable for large n.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * 51) using the fixed-count approach per window, which is effectively O(n). Space complexity is O(51) for the negative frequency array.

What Interviewers Usually Probe

Ask for maintaining a frequency of negative numbers efficiently.
Check if candidate recognizes the fixed bound optimization for nums[i].
Expect sliding window plus hash or array count discussion.

Common Pitfalls or Variants

Common pitfalls

Not updating the counts correctly when the window slides.
Returning the xth smallest across all numbers instead of negatives only.
Using a full sort of each window instead of frequency-based lookup.

Follow-up variants

Compute the maximum negative number in each sliding window of size k.
Return the sum of x smallest negative numbers for each subarray.
Find the xth largest negative number instead of smallest in each window.

FAQ

What is the core pattern in Sliding Subarray Beauty?

It combines array scanning with a hash or frequency map to track negative numbers within each sliding window.

How do I find the xth smallest negative efficiently?

Maintain a frequency array or hash for negatives and accumulate counts to locate the xth smallest without full sorting.

Can this approach handle large arrays?

Yes, using a fixed-size frequency array and sliding window updates, it works efficiently for arrays up to length 10^5.

What happens if a window has fewer than x negative numbers?

Return 0 for that window, as defined in the problem statement.

Why is the negative frequency map better than sorting each window?

It reduces time complexity from O(k log k) per window to O(1) per update using bounded counts, crucial for large n.

terminal

Solution

Solution 1: Sliding Window

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        def f(x: int) -> int:
            s = 0
            for i in range(50):
                s += cnt[i]
                if s >= x:
                    return i - 50
            return 0

        cnt = [0] * 101
        for v in nums[:k]:
            cnt[v + 50] += 1
        ans = [f(x)]
        for i in range(k, len(nums)):
            cnt[nums[i] + 50] += 1
            cnt[nums[i - k] + 50] -= 1
            ans.append(f(x))
        return ans

Solution 2: Double Priority Queue (Min-Max Heap) + Delayed Deletion

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        def f(x: int) -> int:
            s = 0
            for i in range(50):
                s += cnt[i]
                if s >= x:
                    return i - 50
            return 0

        cnt = [0] * 101
        for v in nums[:k]:
            cnt[v + 50] += 1
        ans = [f(x)]
        for i in range(k, len(nums)):
            cnt[nums[i] + 50] += 1
            cnt[nums[i - k] + 50] -= 1
            ans.append(f(x))
        return ans

Continue Practicing

#2747 count zero request servers #2537 count the number of good subarrays #2781 length of the longest valid substring