LeetCode 2653 - Sliding Subarray Beauty

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sliding Window

Solution

Problem Understanding

The problem asks us to compute the beauty of every contiguous subarray of size k within a given integer array nums. The beauty of a subarray is defined as the xth smallest negative number in that subarray. If a subarray contains fewer than x negative numbers, the beauty is 0.

In simpler terms, for each window of k elements sliding from left to right across the array, we need to identify all negative numbers, sort them in ascending order, and pick the xth one if it exists. Otherwise, we return 0.

The inputs are constrained as follows: 1 <= n <= 10^5 means the array can be very large, so naive solutions with O(n_k_log(k)) complexity may be too slow. Each element ranges from -50 to 50, a relatively small range that allows optimization via counting techniques. Edge cases include windows with no negatives, windows where x exceeds the number of negative numbers, and arrays with repeated negative numbers.

Important edge cases include subarrays with exactly x-1 negative numbers, arrays entirely negative or entirely non-negative, and k = 1 which reduces each subarray to a single element.

Approaches

Brute Force Approach

The brute-force method involves iterating over all subarrays of size k. For each subarray, we collect all negative numbers, sort them, and then select the xth smallest negative number. If there are fewer than x negative numbers, we return 0. This approach is correct but inefficient because sorting each subarray costs O(k log k), and there are n-k+1 such subarrays, leading to O(n * k log k) time complexity, which is too slow for large arrays.

Optimal Approach

The optimal approach leverages the small range of numbers [-50, 50] using a counting array. We maintain a frequency array of size 51 for negative numbers. As the window slides, we increment the count for the incoming number and decrement the count for the outgoing number. To find the xth negative number in the current window, we iterate through the counts of negative numbers in ascending order until we reach the cumulative count >= x. This approach avoids sorting and reduces time complexity to O(n * 50), effectively O(n), which is efficient for large inputs.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * k log k)	O(k)	Sorts each subarray of size k
Optimal	O(n * 50) ~ O(n)	O(51)	Uses counting array for negatives in fixed range

Algorithm Walkthrough

Initialize a frequency array count of size 51 to store the counts of negative numbers from -50 to -1.
Preprocess the first window of size k: for each negative number, increment its count in the array.
Determine the beauty of the first window by iterating through the count array, summing counts, and returning the xth negative if it exists; otherwise return 0.
Slide the window by one index to the right: decrement the count of the outgoing element if negative, and increment the count of the incoming element if negative.
After each slide, compute the beauty for the current window using the same counting method.
Append each beauty value to the result list.
Return the final result list after processing all windows.

Why it works: By maintaining counts of negative numbers and updating only for the window edges, we guarantee that the count array always accurately represents the negative numbers in the current window. Since the negative number range is fixed, computing the xth smallest negative is efficient and correct.

Python Solution

from typing import List

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        count = [0] * 51  # index 0 represents -50, index 50 represents 0
        res = []
        
        def get_beauty():
            cum = 0
            for i in range(50):  # only negative numbers -50 to -1
                cum += count[i]
                if cum >= x:
                    return i - 50
            return 0
        
        # initialize first window
        for i in range(k):
            if nums[i] < 0:
                count[nums[i] + 50] += 1
        
        res.append(get_beauty())
        
        for i in range(k, len(nums)):
            out_num = nums[i - k]
            in_num = nums[i]
            if out_num < 0:
                count[out_num + 50] -= 1
            if in_num < 0:
                count[in_num + 50] += 1
            res.append(get_beauty())
        
        return res

Explanation: We use a fixed-size count array to represent negatives. nums[i] + 50 maps -50..-1 to 0..49. For each window slide, we adjust counts for outgoing and incoming elements and calculate the beauty efficiently without sorting.

Go Solution

func getSubarrayBeauty(nums []int, k int, x int) []int {
    count := make([]int, 51) // index 0 for -50
    res := make([]int, 0, len(nums)-k+1)

    getBeauty := func() int {
        cum := 0
        for i := 0; i < 50; i++ { // only negative numbers
            cum += count[i]
            if cum >= x {
                return i - 50
            }
        }
        return 0
    }

    for i := 0; i < k; i++ {
        if nums[i] < 0 {
            count[nums[i]+50]++
        }
    }
    res = append(res, getBeauty())

    for i := k; i < len(nums); i++ {
        outNum := nums[i-k]
        inNum := nums[i]
        if outNum < 0 {
            count[outNum+50]--
        }
        if inNum < 0 {
            count[inNum+50]++
        }
        res = append(res, getBeauty())
    }
    return res
}

Go-specific notes: Go slices are used for the result array. The count array size and negative mapping logic mirrors the Python version. No extra edge handling is needed because the function is guaranteed to have k <= len(nums).

Worked Examples

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

Window	Negative Numbers	Sorted	2nd Smallest	Beauty
[1,-1,-3]	[-1,-3]	[-3,-1]	-1	-1
[-1,-3,-2]	[-1,-3,-2]	[-3,-2,-1]	-2	-2
[-3,-2,3]	[-3,-2]	[-3,-2]	-2	-2

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

Example 2: nums = [-1,-2,-3,-4,-5], k=2, x=2

Window	Negative Numbers	Sorted	2nd Smallest	Beauty
[-1,-2]	[-1,-2]	[-2,-1]	-1	-1
[-2,-3]	[-2,-3]	[-3,-2]	-2	-2
[-3,-4]	[-3,-4]	[-4,-3]	-3	-3
[-4,-5]	[-4,-5]	[-5,-4]	-4	-4

Result: [-1,-2,-3,-4]

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

Window	Negative Numbers	Sorted	1st Smallest	Beauty
[-3,1]	[-3]	[-3]	-3	-3
[1,2]	[]	[]	0	0
[2,-3]	[-3]	[-3]	-3	-3
[-3,0]	[-3]	[-3]	-3	-3
[0,-3]	[-3]	[-3]	-3	-3

Result: [-3,0,-3,-3,-3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * 50) ~ O(n)	Each element enters and exits the window once, counting array iteration takes constant time (max 50)
Space	O(51)	Fixed size count array for negative numbers

The complexity is efficient because the range of negative numbers is small and does not scale with n. Sliding window updates are constant time.

Test Cases

# Provided examples
assert Solution().getSubarrayBeauty([1,-1,-3,-2,3], 3, 2) == [-1,-2,-2]