Sliding Subarray Beauty — Editorial

Opening the reading…

Intuitionthe bounded value range makes each window query small

The beauty is an order statistic, but only among negative values. For a window, sort its negative numbers mentally from -50 upward. The x-th value in that order is the beauty; if the count of negatives never reaches x, the answer stays 0. Because every number lies between -50 and 50, you do not need to store or sort the window itself to find that position.

Keep a frequency table for the values in the current window. When the window moves one position, one value enters and one value leaves, so only two counts change. To find the beauty, scan the negative buckets from -50 to -1 and accumulate their counts. The first value whose running count reaches x is exactly the x-th smallest negative integer.

Approach

Create a frequency array of length 101 and map each value v to index v + 50, because this gives every value from -50 through 50 a valid nonnegative index.

Process nums from left to right, adding nums[i] to its bucket, because the current window must include the newest element before its beauty can be evaluated.

When i >= k, remove nums[i - k] from its bucket, because that element is exactly one position behind the new window's left edge and must not remain counted.

When i >= k - 1, scan values v from -50 to -1 and add their frequencies to a running negative count, because this order is the sorted order needed for the x-th smallest negative.

Stop at the first v whose running count is at least x and use v as the beauty, because every earlier negative value has already accounted for all smaller negative occurrences.

If the scan ends without reaching x, keep the beauty as 0, because the window contains fewer than x negative integers.

Append one beauty after each complete window and return the result, because a length-k array ending at i corresponds to exactly one answer in left-to-right order.

Complexitythe value range is fixed by the problem

MEASURE	BOUND	WHY
Time	O(n)	Each of the n elements is added once and, after the first window, each leaving element is removed once. Each completed window scans at most the 50 negative values, which is a fixed bound, so the total is n times a constant.
Space	O(1) extra	The frequency array always has 101 entries, regardless of n, and the counters use constant space. The returned result is required output and is excluded from the extra-space bound.

Here n is the length of nums. The constants 101 and 50 come from the fixed value range -50 to 50.

Annotated solutionC++ · fixed-size sliding window with frequency buckets

CPPMaintain the current window's frequencies, then scan the negative buckets to find its beauty.

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
        int n = nums.size();
        vector<int> freq(101, 0);
        vector<int> result;

        for (int i = 0; i < n; ++i) {
            freq[nums[i] + 50]++;

            if (i >= k) {
                freq[nums[i - k] + 50]--;
            }

            if (i >= k - 1) {
                int count = 0;
                int beauty = 0;

                for (int value = -50; value < 0; ++value) {
                    count += freq[value + 50];
                    if (count >= x) {
                        beauty = value;
                        break;
                    }
                }

                result.push_back(beauty);
            }
        }

        return result;
    }
};

The order of the update lines matters. The new value is inserted first, and the value k positions behind it is removed next. At index i, those operations leave exactly the indices from i - k + 1 through i in the frequency table. The answer check waits until i >= k - 1, which is the first index where a complete window exists.