Skip to main content

Sliding Window

Sliding Subarray Beauty Solution In C++/Java/Python/JS

Problem Description

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

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.

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. 

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 <= 105
  • 1 <= k <= n
  • 1 <= x <= k 
  • -50 <= nums[i] <= 50
💡
Try Solving "Sliding Subarray Beauty" Yourself First !!
Figuring out "Sliding Subarray Beauty" can be solved using different approaches. We will first figure out the most intuitive approach and move to the optimal approach if exists. Let's sit with a pen and paper and figure out the algorithm !!

Optimal Approach

Intuition

We are given a list of integers. Some are positive, some are zero, and some are negative. The task is: for every subarray of size k, find the x-th smallest negative number. If there are fewer than x negative numbers in that window, we return 0.

This might seem straightforward at first glance, but it quickly becomes non-trivial as the input size grows. Let's work through it systematically and build our understanding step by step.

Problem Breakdown

We are provided with:

  • An array of n integers, which may include positives, negatives, or zeros.
  • A window size k, which defines the length of each subarray.
  • A number x, which tells us we need the x-th smallest negative number in each window.

For every sliding window of size k (as we move from left to right), we need to determine:

  • The x-th smallest negative number in the current window.
  • If there are fewer than x negative numbers, return 0.

Let’s walk through an example

Consider the following:
nums = [4, -5, -2, -8, 6], k = 3, x = 2

All subarrays of size k = 3 are:

  1. [4, -5, -2] → Negatives: [-5, -2] → Sorted: [-5, -2] → 2nd smallest = -2
  2. [-5, -2, -8] → Negatives: [-5, -2, -8] → Sorted: [-8, -5, -2] → 2nd smallest = -5
  3. [-2, -8, 6] → Negatives: [-2, -8] → Sorted: [-8, -2] → 2nd smallest = -2

Final output: [-2, -5, -2]

How Many Subarrays Are There?

Given an array of size n and a window size k, there are exactly n - k + 1 subarrays to examine. For large arrays, such as n = 100,000 and k = 1,000, this results in 99,001 windows. It is critical that we avoid redundant computation for each of these.

Naive Approach

For each window:

  1. Extract the k elements.
  2. Filter out only the negative numbers.
  3. Sort them.
  4. Pick the x-th element, if it exists.

While this is acceptable for small arrays, it becomes inefficient for larger inputs. The time complexity is:

O((n - k + 1) * k log k)

This is due to sorting each window's negatives. With large values of k and n, this becomes infeasible.

Can We Improve This by Sliding the Window?

Let us analyze how the content of the window changes:

Suppose the first window is: [-4, -2, -3]

This gives us the 2nd smallest negative as -3.

When we slide the window by one: [-2, -3, 5]

What has changed?

  • -4 has exited the window.
  • 5 has entered the window.

This suggests a useful observation:

The new window is essentially the old window with one number removed and one new number added.

Thus, we do not need to rebuild the entire structure for each window. Instead, we can incrementally update our data as the window slides forward.

This leads to the next important question.

How Do We Efficiently Track the x Smallest Negatives?

One option is to maintain a list of negative numbers in the current window. Every time we move the window, we remove the outgoing number (if negative), add the incoming one (if negative), then sort and retrieve the x-th smallest.

However, sorting each time still costs O(k log k) in the worst case.

Alternatives like heaps or balanced trees (e.g., TreeSet) can reduce insert/remove operations to O(log k), but we still incur overhead — especially when k is large.

Is there a more optimal way?

What if we do not store the negative numbers at all, but instead store how many times each possible negative value appears?

This leads to a key insight.

A Key Observation: The Numbers Are Bounded

The problem states:

-50 <= nums[i] <= 50

That means there are only 101 possible values in total.

So instead of sorting or maintaining full data structures, we can simply:

  • Create a frequency array of size 101: freq[101]
  • Each index i in freq will represent the number (i - 50)
  • freq[i] will track how many times (i - 50) appears in the current window

In this representation:

  • freq[0] corresponds to -50
  • freq[49] corresponds to -1
  • freq[50] corresponds to 0
  • freq[100] corresponds to 50

This allows us to efficiently maintain a histogram of all numbers within the window, and particularly, the negative values.

How Do We Retrieve the x-th Smallest Negative?

To find the x-th smallest negative value:

  1. Scan the freq array from index 0 to 49 (which represents -50 to -1)
  2. Keep a running count of how many negative numbers we have seen so far
  3. Once the running count reaches x, return (i - 50)

If the count does not reach x, then the window does not contain x negative numbers, and we return 0.

This operation runs in constant time since the range is fixed and small.

Let us walk through a small example:

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

We slide a window of size 3 over the array and look for the 2nd smallest negative number in each window.

Step 1: First Window → [-3, -1, 0]

We update freq as follows:

  • -3 + 50 = 47 → freq[47] = 1
  • -1 + 50 = 49 → freq[49] = 1
  • 0 + 50 = 50 → freq[50] = 1

Now we scan freq[0] to freq[49]:

  • freq[47] = 1 → 1st smallest negative → -3
  • freq[49] = 1 → 2nd smallest negative → -1

Answer for this window: -1

Step 2: Next Window → [-1, 0, 2]

Slide the window forward:

  • Remove -3: freq[47]-- → now freq[47] = 0
  • Add 2: 2 + 50 = 52 → freq[52]++ → now freq[52] = 1

Now scan freq[0] to freq[49]:

  • freq[47] = 0 → skip
  • freq[49] = 1 → 1st smallest negative → -1
  • No further negatives available

Answer for this window: 0

Final Output: [-1, 0]

This confirms that our frequency array approach tracks the negative numbers effectively and retrieves the required element efficiently.

Summary

We have now explored how to solve the Sliding Subarray Beauty problem using a highly efficient approach based on frequency tracking.

Instead of sorting each window or rebuilding data structures repeatedly, we:

  • Leveraged the fact that the input numbers lie in a small, fixed range
  • Used a simple frequency array to count occurrences
  • Scanned a small part of the array to find the result in constant time
  • Updated the frequency in constant time as the window moved

This is the essence of an optimized sliding window strategy: no unnecessary recomputation, no extra complexity — just precise updates and fast queries.

Let's now see how our algorithm looks!

Sliding Subarray Beauty Algorithm

  • We initialize a frequency array freq[101] to keep count of all numbers in the current window, since the possible values are bounded from -50 to 50.
  • We map each number in the range [-50, 50] to an index [0, 100] using the formula: index = num + 50.
  • We fill the first window of size k by updating the frequency array accordingly.
  • We compute the x-th smallest negative by scanning the first 50 entries of the frequency array (which represent numbers from -50 to -1), keeping a running count of how many negatives we’ve seen.
  • If the count reaches x, we record that number as the beauty for the current window. If we don’t find x negatives, we record 0.
  • We then slide the window one position at a time:
    • We decrement the frequency of the number leaving the window.
    • We increment the frequency of the number entering the window.
    • We repeat the process of scanning for the x-th smallest negative.
  • We continue this until we have processed all windows of size k.
  • We return the list of all computed beauty values for each window.

Approach

  • Initialize Frequency Array: Create freq[101] to count elements in the window, where freq[i] maps to number i - 50.
  • Build First Window: Add the first k elements into freq.
  • Get Beauty of First Window: Scan freq[0] to freq[49] to find the x-th smallest negative, or return 0 if not enough.
  • Slide the Window:
    For each index from k to n - 1:
    – Remove nums[i - k] from freq.
    – Add nums[i] to freq.
    – Again, find the x-th smallest negative from freq.
  • Collect Results: Store each result and return the final list after all windows are processed.

Dry-Run

Input: nums = [3, -2, -5, 6, -1, 4, -3, 0], k = 4, x = 2
Output: [-2, -2, -1, -1, -1]

Explanation:

We slide a window of size 4 over the array and, for each window, find the 2nd smallest negative number. If there are fewer than 2 negative numbers, we return 0.

Step 1: First Window → [3, -2, -5, 6]

We update freq[101] as follows:

  • 3 + 50 = 53 → freq[53] = 1
  • -2 + 50 = 48 → freq[48] = 1
  • -5 + 50 = 45 → freq[45] = 1
  • 6 + 50 = 56 → freq[56] = 1

Now scan freq[0] to freq[49]:

  • freq[45] = 1 → 1st smallest negative → -5
  • freq[48] = 1 → 2nd smallest negative → -2

Answer for this window: -2

Step 2: Next Window → [-2, -5, 6, -1]

Slide the window:

  • Remove 3: 3 + 50 = 53 → freq[53]-- → now freq[53] = 0
  • Add -1: -1 + 50 = 49 → freq[49]++ → now freq[49] = 1

Now scan freq[0] to freq[49]:

  • freq[45] = 1 → 1st smallest negative → -5
  • freq[48] = 1 → 2nd smallest negative → -2

Answer for this window: -2

Step 3: Next Window → [-5, 6, -1, 4]

Slide the window:

  • Remove -2: -2 + 50 = 48 → freq[48]-- → now freq[48] = 0
  • Add 4: 4 + 50 = 54 → freq[54]++ → now freq[54] = 1

Now scan freq[0] to freq[49]:

  • freq[45] = 1 → 1st smallest negative → -5
  • freq[49] = 1 → 2nd smallest negative → -1

Answer for this window: -1

Step 4: Next Window → [6, -1, 4, -3]

Slide the window:

  • Remove -5: -5 + 50 = 45 → freq[45]-- → now freq[45] = 0
  • Add -3: -3 + 50 = 47 → freq[47]++ → now freq[47] = 1

Now scan freq[0] to freq[49]:

  • freq[47] = 1 → 1st smallest negative → -3
  • freq[49] = 1 → 2nd smallest negative → -1

Answer for this window: -1

Step 5: Next Window → [-1, 4, -3, 0]

Slide the window:

  • Remove 6: 6 + 50 = 56 → freq[56]-- → now freq[56] = 0
  • Add 0: 0 + 50 = 50 → freq[50]++ → now freq[50] = 1

Now scan freq[0] to freq[49]:

  • freq[47] = 1 → 1st smallest negative → -3
  • freq[49] = 1 → 2nd smallest negative → -1

Answer for this window: -1

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

Sliding Subarray Beauty Solution

Now let's checkout the "Sliding Subarray Beauty" in C++, Java, Python and JavaScript.

"Sliding Subarray Beauty" Code in all Languages.
1. Sliding Subarray Beauty solution in C++ Try on Compiler 
class Solution {
public:

    // Method to return the beauties of all subarrays with length k.
    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {

        // Total number of elements in nums
        int length = nums.size();

        // Frequency array with a size of 101, allowing for offset to handle negative numbers.
        vector<int> count(101, 0);

        // Initialize the count array with the first ‘k’ elements in nums.
        for (int i = 0; i < k; ++i) {
            count[nums[i] + 50]++;
        }

        // Result array to store beauty of each subarray of length k.
        vector<int> beautyValues(length - k + 1);

        // Store the beauty of the first subarray.
        beautyValues[0] = calculateBeauty(count, x);

        // Sliding window approach to calculate beauty for remaining subarrays of length k.
        for (int end = k, start = 1; end < length; ++end) {

            // Include the next element in the window and update its count.
            count[nums[end] + 50]++;

            // Exclude the element that is now outside the window and update its count.
            count[nums[end - k] + 50]--;

            // Calculate beauty for the new subarray and store it.
            beautyValues[start++] = calculateBeauty(count, x);
        }

        return beautyValues;
    }

private:

    // Helper method to calculate beauty using the frequency count array and value x.
    int calculateBeauty(vector<int>& count, int x) {

        int sum = 0;

        // Iterate over the count array to calculate cumulative sum.
        for (int i = 0; i < 50; ++i) {

            sum += count[i];

            // If the cumulative sum is at least x, return the value representing beauty.
            if (sum >= x) {
                return i - 50;
            }
        }

        // If beauty couldn't be determined within loop range, return 0.
        return 0;
    }
};

2. Sliding Subarray Beauty Solution in Java Try on Compiler 
public class Solution {

    // Method to return the beauties of all subarrays with length k.
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {

        // Total number of elements in nums
        int length = nums.length;

        // Frequency array with a size of 101, allowing for offset to handle negative numbers.
        // Offsetting values by 50 to allow for negative values in nums.
        int[] count = new int[101];

        // Initialize the count array with the first ‘k’ elements in nums.
        for (int i = 0; i < k; ++i) {
            count[nums[i] + 50]++;
        }

        // Result array to store beauty of each subarray of length k.
        int[] beautyValues = new int[length - k + 1];

        // Store the beauty of the first subarray.
        beautyValues[0] = calculateBeauty(count, x);

        // Sliding window approach to calculate beauty for remaining subarrays of length k.
        for (int end = k, start = 1; end < length; ++end) {

            // Include the next element in the window and update its count.
            count[nums[end] + 50]++;

            // Exclude the element that is now outside the window and update its count.
            count[nums[end - k] + 50]--;

            // Calculate beauty for the new subarray and store it.
            beautyValues[start++] = calculateBeauty(count, x);
        }

        return beautyValues;
    }

    // Helper method to calculate beauty using the frequency count array and value x.
    private int calculateBeauty(int[] count, int x) {

        int sum = 0;

        // Iterate over the count array to calculate cumulative sum.
        for (int i = 0; i < 50; ++i) {

            sum += count[i];

            // If the cumulative sum is at least x, return the value representing beauty.
            if (sum >= x) {
                return i - 50; // Offset by 50 to get the actual value.
            }
        }

        // If beauty couldn't be determined within loop range, return 0.
        return 0;
    }

}

3. Sliding Subarray Beauty Solution in Python Try on Compiler 
class Solution:

    # Method to return the beauties of all subarrays with length k.
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:

        # Total number of elements in nums
        length = len(nums)

        # Frequency array with a size of 101, allowing for offset to handle negative numbers.
        count = [0] * 101

        # Initialize the count array with the first ‘k’ elements in nums.
        for i in range(k):
            count[nums[i] + 50] += 1

        # Result array to store beauty of each subarray of length k.
        beauty_values = [0] * (length - k + 1)

        # Store the beauty of the first subarray.
        beauty_values[0] = self.calculate_beauty(count, x)

        # Sliding window approach to calculate beauty for remaining subarrays of length k.
        for end in range(k, length):

            # Include the next element in the window and update its count.
            count[nums[end] + 50] += 1

            # Exclude the element that is now outside the window and update its count.
            count[nums[end - k] + 50] -= 1

            # Calculate beauty for the new subarray and store it.
            beauty_values[end - k + 1] = self.calculate_beauty(count, x)

        return beauty_values

    # Helper method to calculate beauty using the frequency count array and value x.
    def calculate_beauty(self, count: List[int], x: int) -> int:

        sum_ = 0

        # Iterate over the count array to calculate cumulative sum.
        for i in range(50):

            sum_ += count[i]

            # If the cumulative sum is at least x, return the value representing beauty.
            if sum_ >= x:
                return i - 50

        # If beauty couldn't be determined within loop range, return 0.
        return 0

4. Sliding Subarray Beauty solution in JavaScript Try on Compiler 
/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var getSubarrayBeauty = function(nums, k, x) {

    // Total number of elements in nums
    const length = nums.length;

    // Frequency array with a size of 101, allowing offset to handle negative numbers (-50 to 50)
    const count = Array(101).fill(0);

    // Initialize the count array with the first 'k' elements in nums
    for (let i = 0; i < k; ++i) {
        count[nums[i] + 50]++;
    }

    // Result array to store beauty of each subarray of length k
    const beautyValues = [];

    // Store the beauty of the first subarray
    beautyValues.push(calculateBeauty(count, x));

    // Sliding window approach to calculate beauty for remaining subarrays of length k
    for (let end = k; end < length; ++end) {

        // Include the next element in the window and update its count
        count[nums[end] + 50]++;

        // Exclude the element that is now outside the window and update its count
        count[nums[end - k] + 50]--;

        // Calculate beauty for the new subarray and store it
        beautyValues.push(calculateBeauty(count, x));
    }

    return beautyValues;

    /**
     * Helper function to calculate beauty using the frequency count array and value x
     * @param {number[]} count
     * @param {number} x
     * @return {number}
     */
    function calculateBeauty(count, x) {

        let sum = 0;

        // Iterate over the count array to calculate cumulative sum (only negatives considered)
        for (let i = 0; i < 50; ++i) {

            sum += count[i];

            // If the cumulative sum is at least x, return the value representing beauty
            if (sum >= x) {
                return i - 50;
            }
        }

        // If beauty couldn't be determined within loop range, return 0
        return 0;
    }
};

Sliding Subarray Beauty Complexity Analysis

Time Complexity: O(n)

The Sliding Subarray Beauty algorithm involves two core operations:

1. Initializing the frequency array with the first k elements:
We compute the frequencies of the first k elements using an integer array of size 101 (to cover values from -50 to 50).
This requires a single pass through the first k elements.
Time complexity: O(k)

2. Sliding the window from left to right:
We iterate from index k to n - 1, simulating each new window by:

  • Removing the outgoing element from the frequency array (constant time)
  • Adding the incoming element to the frequency array (constant time)
  • Scanning the frequency array (first 50 indices) to find the x-th smallest negative (also constant time, since the array is always size 101)
  • Since all operations inside the loop are constant time, and we perform this for n - k windows,
    Time complexity: O(n - k)

Thus, the overall time complexity is: O(k) + O(n - k) = O(n),
where n is the size of the input array.

Space Complexity: O(n)

Auxiliary Space Complexity:
Auxiliary space refers to the additional space used by the algorithm, excluding the input.

  • Frequency Array:
    We use a fixed-size integer array freq[101] to store counts for numbers ranging from -50 to 50.
    This is a constant-size structure and does not depend on the input size.
    Space: O(1)
  • Result List:
    We build a result list of size n - k + 1, storing one integer per window.
    Space: O(n - k + 1), which is proportional to the number of windows.
  • Loop counters and temporary variables:
    Variables used for indexing, counting, and temporary computations are constant in number.
    Space: O(1)

Total Space Complexity:

  • Input array:
    The input array nums occupies O(n) space, where n is the length of the array.
  • Additional space:
    The result list takes O(n - k + 1), and all other extras (like freq) are O(1).

Therefore, total space complexity: O(n + n - k + 1 + 1) = O(n)

Similar Problems

Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Count Number of Nice Subarrays

Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.