LeetCode Solutions Blog

Sliding Subarray Beauty

Number: 2751

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer array nums of length n, for each contiguous subarray of size k, compute its beauty. The beauty of a subarray is defined as the xth smallest negative integer in that subarray; if the subarray contains fewer than x negative numbers, the beauty is 0.

Key Insights

Use a sliding window of size k.
Since we only care about negative numbers (range between -50 and -1), maintain their frequency count in the current window.
For each window, iterate over possible negative numbers (from -50 to -1) in order to determine the xth smallest negative.
Update the frequency count when sliding the window (remove the outgoing element and add the incoming element).

Space and Time Complexity

Time Complexity: O(n * 50) ≈ O(n) because for each window we iterate over a constant range (50).
Space Complexity: O(1) since the extra space used (frequency array of fixed size 50) does not depend on n.

Solution

We use a sliding window approach combined with a frequency array for negative numbers. For each window:

Update the frequency of negative numbers.
To find the xth smallest negative value in the window, iterate from -50 to -1; subtract the count of each negative number from x until x becomes <= 0. The current number is the xth negative. If not found, the beauty is 0.
Slide the window by removing the leftmost element (update frequency if negative) and adding the new incoming element (update frequency if negative).

This approach leverages the small range of negative numbers for an efficient solution.

Code Solutions

# Python solution with detailed line-by-line comments

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        # Initialize a frequency array for negatives from -50 to -1.
        # We use an array of size 51, where index i corresponds to negative number i.
        freq = [0] * 51  
        
        # Helper function to update frequency count if the number is negative.
        def update(num, delta):
            if num < 0:
                # Convert negative value to index (e.g., -1 maps to index 1, -50 maps to index 50)
                freq[-num] += delta
        
        n = len(nums)
        result = []
        
        # Initialize the frequency based on the first window
        for i in range(k):
            update(nums[i], 1)
        
        # Compute beauty for the first window
        def get_beauty(x):
            # xth smallest negative: iterate from -50 (index 50) to -1 (index 1) but in ascending order means -50 is smallest.
            # However, since negative numbers are ordered with larger absolute value first, we iterate from index=50 down to 1.
            # Alternatively, we can iterate from -50 to -1 in increasing order.
            count = x
            # iterate from -50 to -1 (i corresponds to absolute value)
            for neg in range(50, 0, -1):
                if freq[neg]:
                    count -= freq[neg]
                    if count <= 0:
                        # Found the xth negative, return it (convert index to negative number)
                        return -neg
            return 0
        
        result.append(get_beauty(x))
        
        # Slide the window from index 1 to n - k
        for i in range(k, n):
            # Remove element going out of the window
            update(nums[i - k], -1)
            # Add new element coming in the window
            update(nums[i], 1)
            result.append(get_beauty(x))
        
        return result