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 xthsmallest integer in the subarray if it is negative , or 0 if there are fewer than x negative integers.

Return an integer array containingn - k + 1 integers, which denote thebeauty of the subarraysin order from the first index in the array.

  • A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8

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 <= 10^5
  • 1 <= k <= n
  • 1 <= x <= k
  • -50 <= nums[i] <= 50

Solution

Method 1 – Sliding Window with Counting (Bucket Sort)

Intuition

Since all numbers are in [-50, 50], we can use a fixed-size frequency array to count negatives in the window. For each window, find the x-th smallest negative by scanning the count array.

Approach

  1. Use a frequency array of size 101 (for -50 to 50).
  2. Slide a window of size k over nums, updating the frequency array as you go.
  3. For each window, scan the negative part of the frequency array to find the x-th smallest negative.
  4. If there are fewer than x negatives, output 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <vector>
using namespace std;
class Solution {
public:
    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
        vector<int> res, cnt(101);
        int n = nums.size();
        for (int i = 0; i < k-1; ++i) cnt[nums[i]+50]++;
        for (int i = k-1; i < n; ++i) {
            cnt[nums[i]+50]++;
            int c = 0, val = 0;
            for (int v = 0; v < 50; ++v) {
                c += cnt[v];
                if (c >= x) { val = v-50; break; }
            }
            if (c < x) val = 0;
            res.push_back(val);
            cnt[nums[i-k+1]+50]--;
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import java.util.*;
class Solution {
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length;
        int[] cnt = new int[101], res = new int[n-k+1];
        for (int i = 0; i < k-1; ++i) cnt[nums[i]+50]++;
        for (int i = k-1; i < n; ++i) {
            cnt[nums[i]+50]++;
            int c = 0, val = 0;
            for (int v = 0; v < 50; ++v) {
                c += cnt[v];
                if (c >= x) { val = v-50; break; }
            }
            if (c < x) val = 0;
            res[i-k+1] = val;
            cnt[nums[i-k+1]+50]--;
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def getSubarrayBeauty(self, nums, k, x):
        n = len(nums)
        cnt = [0]*101
        res = []
        for i in range(k-1):
            cnt[nums[i]+50] += 1
        for i in range(k-1, n):
            cnt[nums[i]+50] += 1
            c = 0
            val = 0
            for v in range(0, 50):
                c += cnt[v]
                if c >= x:
                    val = v-50
                    break
            if c < x:
                val = 0
            res.append(val)
            cnt[nums[i-k+1]+50] -= 1
        return res

Complexity

  • ⏰ Time complexity: O(n * C) where C=50 (constant), so effectively O(n).
  • 🧺 Space complexity: O(1) — Only a fixed-size count array is used.