Problem Description

You are given an integer array nums containing n integers, and you need to find the "beauty" of each subarray of size k.

The beauty of a subarray is defined as:

• The x-th smallest integer in the subarray if that integer is negative
• 0 if there are fewer than x negative integers in the subarray

Your task is to return an integer array containing n - k + 1 integers, where each integer represents the beauty of the corresponding subarray of size k, in the order they appear when sliding through the original array from left to right.

For example, if you have an array nums and parameters k and x:

• You would look at the first k elements, find all negative numbers, and determine if there's an x-th smallest negative number
• Then slide the window one position to the right and repeat
• Continue until you've checked all possible subarrays of size k

Key points to understand:

• A subarray is a contiguous sequence of elements from the array
• Only negative integers count toward finding the x-th smallest
• If a subarray doesn't have at least x negative integers, its beauty is 0
• The result array will have n - k + 1 elements (one beauty value for each possible subarray of size k)

Intuition

The key insight is recognizing that we need to efficiently find the x-th smallest negative number in each sliding window of size k. Since the problem involves repeatedly finding order statistics (the x-th smallest element) as we slide through the array, we need a data structure that can quickly update and query.

The critical observation is that the array elements are bounded within [-50, 50]. This small range suggests we can use counting sort principles rather than comparison-based sorting. Instead of sorting each window from scratch, we can maintain a frequency count of all elements in the current window.

Why does this work well? Consider:

1. With only 101 possible values (-50 to 50), we can use an array cnt of size 101 to track frequencies
2. To handle negative indices, we shift all values by adding 50 (so -50 becomes index 0, -49 becomes index 1, etc.)
3. When the window slides, we only need to:
   • Increment the count for the new element entering the window
   • Decrement the count for the element leaving the window
   • This is O(1) for updates

To find the x-th smallest negative number:

• We iterate through the first half of our cnt array (indices 0 to 49, representing values -50 to -1)
• We accumulate counts until we reach x negative numbers
• The index where we stop (converted back to the original value) gives us our answer
• If we can't find x negative numbers, we return 0

This approach transforms what could be an O(k log k) sorting operation for each window into an O(50) counting operation, which is effectively O(1) since 50 is a constant. The sliding window technique ensures we only update counts incrementally rather than recounting everything for each subarray.

Learn more about Sliding Window patterns.

Solution Approach

The solution uses a sliding window technique combined with counting sort to efficiently find the beauty of each subarray.

Data Structure Setup:

• Create a counting array cnt of size 101 to track frequencies of elements in the range [-50, 50]
• Add 50 to each element to map them to indices [0, 100] (avoiding negative indices)

Helper Function f(x): This function finds the x-th smallest negative number in the current window:

def f(x: int) -> int:
    s = 0
    for i in range(50):  # Only check indices 0-49 (representing -50 to -1)
        s += cnt[i]
        if s >= x:
            return i - 50  # Convert back to original value
    return 0  # If fewer than x negative numbers exist

• Iterate through indices 0 to 49 (representing negative values -50 to -1)
• Accumulate the count s of negative numbers seen so far
• When s >= x, we've found the x-th smallest negative number
• Return i - 50 to convert the index back to the actual negative value
• Return 0 if we can't find x negative numbers

Main Algorithm:

1. Initialize the first window:

   cnt = [0] * 101
   for v in nums[:k]:
       cnt[v + 50] += 1

   • Fill the counting array with the first k elements
   • Add 50 to each value to get the correct index

2. Calculate beauty for the first window:

   ans = [f(x)]

3. Slide the window and update:

   for i in range(k, len(nums)):
       cnt[nums[i] + 50] += 1        # Add new element
       cnt[nums[i - k] + 50] -= 1    # Remove old element
       ans.append(f(x))               # Calculate beauty

   • For each new position, add the incoming element to cnt
   • Remove the outgoing element (the one that's now k positions behind)
   • Calculate and store the beauty value for the new window

Time Complexity: O(n * 50) where n is the length of the array. Since 50 is constant, this is effectively O(n).

Space Complexity: O(1) for the counting array (fixed size 101) plus O(n - k + 1) for the result array.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• nums = [1, -1, -3, -2, 3]
• k = 3 (window size)
• x = 2 (find 2nd smallest negative)

Step 1: Initialize counting array and first window

Create cnt array of size 101 (all zeros initially). Process first window [1, -1, -3]:

• 1 + 50 = 51: cnt[51] = 1
• -1 + 50 = 49: cnt[49] = 1
• -3 + 50 = 47: cnt[47] = 1

Step 2: Find beauty of first window [1, -1, -3]

Call f(2) to find 2nd smallest negative:

• Check indices 0-49 (representing -50 to -1)
• At index 47: s = 0 + 1 = 1 (found 1 negative: -3)
• At index 49: s = 1 + 1 = 2 (found 2 negatives: -3, -1)
• Since s >= 2, return 49 - 50 = -1

Beauty of first window = -1

Step 3: Slide to second window [-1, -3, -2]

Update counts:

• Remove nums[0] = 1: cnt[51] -= 1 → cnt[51] = 0
• Add nums[3] = -2: cnt[48] += 1 → cnt[48] = 1

Current cnt has:

• cnt[47] = 1 (representing -3)
• cnt[48] = 1 (representing -2)
• cnt[49] = 1 (representing -1)

Call f(2):

• At index 47: s = 1 (found -3)
• At index 48: s = 2 (found -3, -2)
• Since s >= 2, return 48 - 50 = -2

Beauty of second window = -2

Step 4: Slide to third window [-3, -2, 3]

Update counts:

• Remove nums[1] = -1: cnt[49] -= 1 → cnt[49] = 0
• Add nums[4] = 3: cnt[53] += 1 → cnt[53] = 1

Current cnt has:

• cnt[47] = 1 (representing -3)
• cnt[48] = 1 (representing -2)

Call f(2):

• At index 47: s = 1 (found -3)
• At index 48: s = 2 (found -3, -2)
• Since s >= 2, return 48 - 50 = -2

Beauty of third window = -2

Final Result: [-1, -2, -2]

The key insight is that we never sort the entire window. Instead, we maintain counts and traverse them in order when needed, making updates O(1) and queries O(50) = O(1).

Solution Implementation

Time and Space Complexity

The time complexity is O(n × 50), where n is the length of the array nums. This is because:

• The sliding window iterates through the array once, taking O(n) time
• For each window position, the function f(x) is called, which iterates through at most 50 elements (indices 0 to 49 of the cnt array, representing negative numbers from -50 to -1)
• Therefore, the total time complexity is O(n × 50)

The space complexity is O(100) or simply O(1) since it's constant. This is because:

• The cnt array has a fixed size of 101 elements to store the frequency count of numbers in the range [-50, 50]
• The ans array stores n - k + 1 results, but this is considered as output space and typically not counted in space complexity analysis
• All other variables use constant space

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Index Mapping for Negative Numbers

One of the most common mistakes is incorrectly mapping array values to counting array indices, especially when dealing with negative numbers.

Pitfall Example:

# WRONG: Forgetting to offset negative values
frequency_count[nums[i]] += 1  # This will cause IndexError for negative values!

# WRONG: Using wrong offset
frequency_count[nums[i] + 51] += 1  # Off-by-one error in offset

Solution: Always use consistent offset of 50 to map the range [-50, 50] to [0, 100]:

frequency_count[value + 50] += 1  # Correct mapping

2. Iterating Through Wrong Range When Finding x-th Smallest

Another critical mistake is iterating through all 101 indices instead of just the negative value range.

Pitfall Example:

def find_xth_smallest_negative(x: int) -> int:
    cumulative_count = 0
    # WRONG: Iterating through all values including positives
    for i in range(101):  
        cumulative_count += frequency_count[i]
        if cumulative_count >= x:
            return i - 50  # This might return a positive number!
    return 0

Solution: Only iterate through indices 0-49 (representing -50 to -1):

def find_xth_smallest_negative(x: int) -> int:
    cumulative_count = 0
    for i in range(50):  # Only negative values
        cumulative_count += frequency_count[i]
        if cumulative_count >= x:
            return i - 50
    return 0

3. Sliding Window Update Order Error

Updating the window in the wrong order or using incorrect indices can lead to wrong results.

Pitfall Example:

# WRONG: Removing wrong element (off-by-one error)
for i in range(k, len(nums)):
    frequency_count[nums[i] + 50] += 1
    frequency_count[nums[i - k - 1] + 50] -= 1  # Wrong! Should be i - k
  
# WRONG: Calculating beauty before updating window
for i in range(k, len(nums)):
    result.append(find_xth_smallest_negative(x))  # Calculate before update
    frequency_count[nums[i] + 50] += 1
    frequency_count[nums[i - k] + 50] -= 1

Solution: Always update the window first (add new, remove old), then calculate beauty:

for i in range(k, len(nums)):
    frequency_count[nums[i] + 50] += 1        # Add new element
    frequency_count[nums[i - k] + 50] -= 1    # Remove element k positions back
    result.append(find_xth_smallest_negative(x))  # Then calculate beauty

4. Misunderstanding the Beauty Definition

Confusing when to return 0 vs the actual value.

Pitfall Example:

def find_xth_smallest_negative(x: int) -> int:
    cumulative_count = 0
    for i in range(50):
        cumulative_count += frequency_count[i]
        if cumulative_count >= x:
            # WRONG: Always returning the value even if it's not negative
            return i - 50
    # WRONG: Returning the x-th smallest regardless of sign
    for i in range(50, 101):  # Checking positive numbers
        cumulative_count += frequency_count[i]
        if cumulative_count >= x:
            return i - 50  # This would return a positive number!
    return 0

Solution: The beauty is specifically the x-th smallest negative integer, or 0 if there aren't enough negative integers:

• Only consider negative values (indices 0-49)
• Return 0 if we can't find x negative numbers
• Never return positive values as beauty