# Sliding Subarray Beauty
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sliding-subarray-beauty)
Canonical: https://scaleengineer.com/dsa/problems/sliding-subarray-beauty
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Hash Table
---
## Problem
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 1:**

**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.

**Example 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. 

**Example 3:**

**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 `

# Approaches
## Brute Force with Sorting
This approach iterates through every possible subarray of size `k`. For each subarray, it identifies all the negative numbers, sorts them, and then finds the `x`-th smallest one to determine the beauty.
**Time:** O(n * k log k)
The outer loop runs `n - k + 1` times. In each iteration, we iterate `k` times to form a list of negative numbers. The size of this list can be up to `k`. Sorting this list takes `O(k log k)` time. Thus, the total time complexity is `O((n - k + 1) * k log k)`. · **Space:** O(n)
We use `O(k)` extra space for the list of negative numbers in each iteration. The result array requires `O(n - k + 1)` space, making the total `O(n)`.
**Pros:** Simple to understand and implement.; Correctly solves the problem for smaller inputs.
**Cons:** Inefficient due to re-computation for each subarray.; Sorting within the loop makes it slow, especially for large `k`.; Does not pass for the given constraints and will likely result in a 'Time Limit Exceeded' error.
### Explanation
The algorithm proceeds as follows:
1.  We initialize an answer array `ans` of size `n - k + 1` to store the beauty of each subarray.
2.  We loop from the first possible starting index `i = 0` up to `n - k`. Each `i` represents the beginning of a new subarray.
3.  For each subarray starting at `i` and of length `k` (i.e., `nums[i...i+k-1]`), we create a temporary list.
4.  We iterate through this subarray and add all negative numbers to our temporary list.
5.  After collecting all negative numbers, we sort this list in ascending order.
6.  We then check the size of the list. If the number of negative elements is less than `x`, the beauty is defined as `0`.
7.  If there are `x` or more negative numbers, the `x`-th smallest negative number is at index `x-1` in the sorted list. This value is the beauty.
8.  We store the calculated beauty in the `ans` array at the corresponding index.
9.  After iterating through all possible subarrays, we return the `ans` array.
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        
        for (int i = 0; i <= n - k; i++) {
            // For each subarray, collect negative numbers
            List<Integer> negatives = new ArrayList<>();
            for (int j = i; j < i + k; j++) {
                if (nums[j] < 0) {
                    negatives.add(nums[j]);
                }
            }
            
            // If there are fewer than x negative numbers, beauty is 0
            if (negatives.size() < x) {
                result[i] = 0;
            } else {
                // Otherwise, sort and find the x-th smallest
                Collections.sort(negatives);
                result[i] = negatives.get(x - 1);
            }
        }
        
        return result;
    }
}
```
### Algorithm
*   Initialize an empty result array `ans`.
*   Iterate with a start index `i` from `0` to `n - k`.
*   For each `i`, create a new list `negatives`.
*   Iterate from `j = i` to `i + k - 1` to form the subarray.
*   If `nums[j]` is negative, add it to the `negatives` list.
*   If `negatives.size() < x`, the beauty is `0`.
*   Otherwise, sort the `negatives` list and the beauty is the element at index `x - 1`.
*   Add the beauty to the `ans` array.
*   Return `ans`.

## Sliding Window with Frequency Array
This approach uses the sliding window technique combined with a frequency map to efficiently calculate the beauty of each subarray. The key observation is that the range of numbers is small (`-50` to `50`), which allows us to use a frequency array (acting as a form of counting sort) to track the counts of negative numbers in the current window. This avoids the costly sorting step in each iteration.
**Time:** O(n)
Initializing the first window takes `O(k)`. The main loop runs `n - k` times. Inside the loop, updating the frequency array takes `O(1)`. The `findXthSmallest` function takes a constant amount of time, `O(C)` where C=50, as it iterates up to 50 times. Therefore, the total time complexity is `O(k + (n - k) * C)`, which simplifies to `O(n)` as C is a small constant. · **Space:** O(n)
The result array requires `O(n - k + 1)` space. The frequency array requires `O(C)` space, where `C` is the range of negative numbers (50). Since `C` is a constant, the total space complexity is dominated by the result array, making it `O(n)`.
**Pros:** Highly efficient, with linear time complexity.; Effectively uses the constraint on the range of input values.; Optimal solution for this problem.
**Cons:** The logic is slightly more complex than the brute-force approach.; This approach is only efficient because the range of values is small and fixed. It would not be suitable if the numbers could be arbitrarily large.
### Explanation
The algorithm works by maintaining a count of each negative number within the current window of size `k`.
1.  We use a frequency array, `freq`, of size 51. We can map each negative number `num` to an index in this array. A convenient mapping is to use `freq[-num]` to store the count of `num`. For example, the count of `-1` is stored at `freq[1]`, `-2` at `freq[2]`, and so on, up to `-50` at `freq[50]`.
2.  First, we process the initial window of `k` elements (`nums[0...k-1]`). We iterate through these elements and update the `freq` array for any negative numbers encountered.
3.  After populating the frequency map for the first window, we find its beauty. To do this, we iterate through our possible negative numbers from smallest to largest (i.e., from `-50` to `-1`). This corresponds to iterating through our `freq` array from index `50` down to `1`. We accumulate the counts until the total count is at least `x`. The number corresponding to the index where this happens is the `x`-th smallest negative number. If we go through all negative numbers and the total count is less than `x`, the beauty is `0`.
4.  We store this first beauty value in our result array.
5.  Then, we slide the window one position at a time from left to right. For each step, we update the `freq` array:
    *   Decrement the count for the element that is leaving the window (if it's negative).
    *   Increment the count for the element that is entering the window (if it's negative).
6.  After each slide, the `freq` array accurately reflects the counts of negative numbers in the new window. We then repeat the process of finding the beauty using the updated `freq` array and store it in our result.
7.  This continues until the window has traversed the entire array.
```java
class Solution {
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        // freq[i] will store the count of number -i.
        // We only care about negative numbers from -1 to -50.
        int[] freq = new int[51]; 

        // Initialize the first window
        for (int i = 0; i < k; i++) {
            if (nums[i] < 0) {
                freq[-nums[i]]++;
            }
        }

        result[0] = findXthSmallest(freq, x);

        // Slide the window
        for (int i = k; i < n; i++) {
            // Add the new element
            if (nums[i] < 0) {
                freq[-nums[i]]++;
            }
            // Remove the old element
            if (nums[i - k] < 0) {
                freq[-nums[i - k]]--;
            }
            
            result[i - k + 1] = findXthSmallest(freq, x);
        }

        return result;
    }

    private int findXthSmallest(int[] freq, int x) {
        int count = 0;
        // Iterate from -50 to -1 to find the x-th smallest
        for (int i = 50; i >= 1; i--) {
            count += freq[i];
            if (count >= x) {
                return -i;
            }
        }
        // If fewer than x negative numbers exist
        return 0;
    }
}
```
### Algorithm
*   Create a frequency array `freq` of size 51 to store counts of negative numbers from -1 to -50.
*   Initialize the first window: iterate from `i = 0` to `k-1`, and if `nums[i]` is negative, increment `freq[-nums[i]]`.
*   Calculate the beauty for the first window by calling a helper function `findXthSmallest` and store it in the result.
*   The `findXthSmallest` function iterates from `i = 50` down to `1` (representing numbers -50 to -1). It accumulates the frequencies. When the accumulated count is `>= x`, it returns `-i`. If the loop completes, it means there are fewer than `x` negative numbers, so it returns `0`.
*   Slide the window from `i = k` to `n-1`:
    *   Decrement the frequency of the element leaving the window, `nums[i-k]`, if it's negative.
    *   Increment the frequency of the element entering the window, `nums[i]`, if it's negative.
    *   Calculate the beauty for the new window using `findXthSmallest` and store it.
*   Return the result array.

# Solutions
### Java

```java
class Solution {
public
  int[] getSubarrayBeauty(int[] nums, int k, int x) {
    int n = nums.length;
    int[] cnt = new int[101];
    for (int i = 0; i < k; ++i) {
      ++cnt[nums[i] + 50];
    }
    int[] ans = new int[n - k + 1];
    ans[0] = f(cnt, x);
    for (int i = k, j = 1; i < n; ++i) {
      ++cnt[nums[i] + 50];
      --cnt[nums[i - k] + 50];
      ans[j++] = f(cnt, x);
    }
    return ans;
  }
private
  int f(int[] cnt, int x) {
    int s = 0;
    for (int i = 0; i < 50; ++i) {
      s += cnt[i];
      if (s >= x) {
        return i - 50;
      }
    }
    return 0;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> getSubarrayBeauty(vector<int> &nums, int k, int x) {
    int n = nums.size();
    int cnt[101]{};
    for (int i = 0; i < k; ++i) {
      ++cnt[nums[i] + 50];
    }
    vector<int> ans(n - k + 1);
    auto f = [&](int x) {
      int s = 0;
      for (int i = 0; i < 50; ++i) {
        s += cnt[i];
        if (s >= x) {
          return i - 50;
        }
      }
      return 0;
    };
    ans[0] = f(x);
    for (int i = k, j = 1; i < n; ++i) {
      ++cnt[nums[i] + 50];
      --cnt[nums[i - k] + 50];
      ans[j++] = f(x);
    }
    return ans;
  }
};

```

### Python

```python
from sortedcontainers import SortedList class Solution : def getSubarrayBeauty ( self , nums : List [ int ], k : int , x : int ) -> List [ int ]: sl = SortedList ( nums [: k ]) ans = [ sl [ x - 1 ] if sl [ x - 1 ] < 0 else 0 ] for i in range ( k , len ( nums )): sl . remove ( nums [ i - k ]) sl . add ( nums [ i ]) ans . append ( sl [ x - 1 ] if sl [ x - 1 ] < 0 else 0 ) return ans
```