2653. Sliding Subarray Beauty

Posted on Edited on In

2653. Sliding Subarray Beauty

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 x^th 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:

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 2^nd smallest negative integer is -1.
The second subarray is `[-1, -3, -2]` and the 2^nd smallest negative integer is -2.
The third subarray is `[-3, -2, 3]`and the 2^nd 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 2^nd smallest negative integer is -1.
For `[-2, -3]`, the 2^nd smallest negative integer is -2.
For `[-3, -4]`, the 2^nd smallest negative integer is -3.
For `[-4, -5]`, the 2^nd 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 1^st smallest negative integer is -3.
For `[1, 2]`, there is no negative integer so the beauty is 0.
For `[2, -3]`, the 1^st smallest negative integer is -3.
For `[-3, 0]`, the 1^st smallest negative integer is -3.
For `[0, -3]`, the 1^st smallest negative integer is -3.

Constraints:

  • n == nums.length
  • 1 <= n <= 10^5
  • 1 <= k <= n
  • 1 <= x <= k
  • -50<= nums[i] <= 50

Hints/Notes

Solution

Language: C++

Because the range of nums array is small, so we can just iterate every possible negative value

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
        const int BIAS = 50;
        vector<int> count(BIAS * 2 + 1, 0);
        int right = 0, n = nums.size();
        vector<int> res(n - k + 1, 0);
        while (right < n) {
            count[nums[right] + 50]++;
            if (right >= k - 1) {
                int left = x;
                for (int i = -50; i < 0; i++) {
                    left -= count[i + 50];
                    if (left <= 0) {
                        res[right - k + 1] = i;
                        break;
                    }
                }
                count[nums[right - k + 1] + BIAS]--;
            }
            right++;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
        multiset<int> mx, mi;
        int n = nums.size(), right = 0;
        vector<int> res;
        while (right < n) {
            int num = nums[right];
            mi.insert(num);
            if (mi.size() > x) {
                auto it = prev(mi.end());
                mx.insert(*it);
                mi.erase(it);
            }
            if (right >= k - 1) {
                auto it = prev(mi.end());
                res.push_back(*it < 0 ? *it : 0);
                // we need to remove l from one of the set
                int l = nums[right - k + 1];
                if (mx.contains(l)) {
                    auto it = mx.lower_bound(l);
                    mx.erase(it);
                } else {
                    auto it = mi.lower_bound(l);
                    mi.erase(it);
                    while (!mx.empty() && mi.size() < x) {
                        it = mx.begin();
                        mi.insert(*it);
                        mx.erase(it);
                    }
                }
            }
            right++;
        }
        return res;
    }
};