2653. Sliding Subarray Beauty


Problem Description

The problem presents a scenario where we are given an array nums consisting of n integers, and we are tasked with determining the "beauty" of every contiguous subarray that is of size k. Beauty in this context is defined as the value of the xth smallest integer in the subarray, but with a twist. If the xth smallest number is negative, that is the beauty. If not, or there are fewer than x negative integers in the subarray, then the beauty is 0. The goal is to create an array that contains the beauty of each subarray starting from the beginning of the nums array, such that we end up with n - k + 1 beauties.

It is important to understand that a subarray is considered a continuous part of the original array and cannot be empty.

In simpler terms, this problem is asking us to look at every possible continuous chunk of k elements in the array, count negative numbers within it and if there are at least x negative numbers, find the xth smallest one, otherwise record a beauty of 0.

Intuition

To solve this problem, a natural approach is to utilize a data structure that can keep numbers sorted as they are added or removed. This way, we can maintain the order of elements in each k-sized subarray in real time without having to sort the subarray on every iteration. This is crucial because sorting every subarray would lead to a high computational complexity, making it inefficient for large arrays.

The solution uses the SortedList data structure from the Python sortedcontainers module which helps maintain a sorted list efficiently. Here's how this works:

  1. We initialize SortedList with the first k elements of the nums array. This automatically keeps these elements sorted.
  2. We record the beauty of the initial subarray. The xth smallest element can be retrieved directly by index x - 1 due to zero-based indexing. If this element is negative, it is the beauty; otherwise, we record 0.
  3. We then slide the window of size k across the array from start to finish. In each step:
    • We remove the leftmost (oldest) element of the subarray from the sorted list since it is no longer in the current window.
    • We add the new element (the one that comes into the window from the right) to the sorted list, keeping the list sorted.
    • We then compute and record the beauty of the new subarray in an analogous manner to step 2.
  4. Once we have slid the window across the entire array, we will have computed the beauty of each subarray, and we return the collection of beauties recorded.

Using this method, we continuously maintain a sorted window of the current subarray, allowing us to efficiently answer queries about its xth smallest element and compute the beauty without re-sorting the entire subarray each time.

Solution Approach

The implementation of the solution uses the SortedList data structure that provides the capability to manage a sorted sequence of numbers efficiently. In Python, SortedList handles changes to the sequence, such as adding or removing elements, while maintaining the sorted order. This capability is key to the solution because it allows us to efficiently manage the min-heap property that makes retrieval of the xth smallest number possible in constant time.

Let's walk through a detailed implementation strategy referencing the code provided:

  1. We instantiate a SortedList with the first k elements of the nums array. This prepares our first subarray and maintains its elements in sorted order.

    1sl = SortedList(nums[:k])
  2. We calculate the beauty of the first subarray immediately. If the (x - 1) index element is negative, this value is recorded as the beauty; otherwise, 0 is recorded. This becomes the first element of our answer list ans.

    1ans = [sl[x - 1] if sl[x - 1] < 0 else 0]
  3. Next, we enter a loop that iterates over nums from the kth index to the end:

    1for i in range(k, len(nums)):
    • For each iteration, the leftmost (oldest) element of the previous subarray is removed from SortedList:
    1sl.remove(nums[i - k])
    • Simultaneously, the next element in the array (nums[i]) is added to SortedList, again maintaining sorting:
    1sl.add(nums[i])
    • We then evaluate the beauty of the current subarray: if the (x - 1) index element is negative, this value is recorded as the beauty; otherwise, 0 is recorded:
    1ans.append(sl[x - 1] if sl[x - 1] < 0 else 0)
  4. Finally, after the loop completes, ans contains the beauty of each subarray. This result is then returned.

    1return ans

By using the SortedList, we avoid the need to sort each subarray individually, as it takes care of maintaining the sorted order upon insertions and deletions. This results in an efficient solution that can handle the sliding window computation in a way that is much faster than a naive solution that would sort every single subarray.

Example Walkthrough

Let's use a small example to illustrate the solution approach described above. Suppose we are given an array nums with elements [-1, 2, -3, 4, -5] and we need to find the beauty of every subarray of size k = 3, where the beauty is defined as the x = 2nd smallest negative integer in the subarray.

  1. Initialize a SortedList with the first k elements of the nums array:

    1sl = SortedList([-1, 2, -3])

    The sorted list would be [-3, -1, 2].

  2. Calculate the beauty of the first subarray:

    1ans = [-1 if sl[1] < 0 else 0]

    Since the element at index 1 (remembering zero-based indexing) is -1, which is negative, we record -1 in ans.

    Now, ans = [-1].

  3. Slide the window and update the SortedList:

    For the next subarray [2, -3, 4], remove the element -1 from sl and add 4:

    1sl.remove(-1)
    2sl.add(4)

    Now sl becomes [-3, 2, 4]. The element at index 1 is now 2, so the beauty of this subarray is 0.

    Update ans to include the new beauty: ans = [-1, 0].

  4. Move the window to the next subarray [4, -5]:

    Remove the leftmost element 2 from sl and add -5:

    1sl.remove(2)
    2sl.add(-5)

    The sorted list now is [-5, -3, 4]. The element at index 1 is -3, which is negative, so this subarray's beauty is -3.

    Update ans to include this new beauty: ans = [-1, 0, -3].

After following these steps, we obtain the final result ans = [-1, 0, -3], which contains the beauty of each contiguous subarray of size k = 3. This array tells us that the first subarray has a beauty value of -1, the second has 0 since there aren't enough negative numbers to consider, and the third subarray has a beauty value of -3.

Using the SortedList, we efficiently calculated the beauty of all subarrays without having to sort each one individually.

Python Solution

1from sortedcontainers import SortedList
2from typing import List  # importing typing module for List type hint
3
4
5class Solution:
6    def get_subarray_beauty(self, nums: List[int], k: int, x: int) -> List[int]:
7        # Create a sorted list with the first 'k' elements of 'nums'
8        sorted_list = SortedList(nums[:k])
9      
10        # Calculate the initial beauty and store it in the result list.
11        # If the x-1 th element (0-indexed) of the sorted list is negative, store it; otherwise, store 0.
12        result = [sorted_list[x - 1] if sorted_list[x - 1] < 0 else 0]
13      
14        # Iterate through the rest of 'nums' starting from index 'k'
15        for i in range(k, len(nums)):
16            # Remove the element that's no longer in the sliding window
17            sorted_list.remove(nums[i - k])
18            # Add the new element to the sorted list
19            sorted_list.add(nums[i])
20          
21            # Calculate the beauty for the new subarray and append it to the result list
22            result.append(sorted_list[x - 1] if sorted_list[x - 1] < 0 else 0)
23      
24        # Return the final list of beauties
25        return result
26

Java Solution

1class Solution {
2    // Method to return the beauties of all subarrays with length k.
3    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
4        int length = nums.length; // Total number of elements in nums
5      
6        // Frequency array with a size of 101, allowing for offset to handle negative numbers.
7        // Offsetting values by 50 to allow for negative values in nums.
8        int[] count = new int[101];
9        // Initialize the count array with the first ‘k’ elements in nums.
10        for (int i = 0; i < k; ++i) {
11            count[nums[i] + 50]++;
12        }
13      
14        // Result array to store beauty of each subarray of length k.
15        int[] beautyValues = new int[length - k + 1];
16        // Store the beauty of the first subarray.
17        beautyValues[0] = calculateBeauty(count, x);
18        // Sliding window approach to calculate beauty for remaining subarrays of length k.
19        for (int end = k, start = 1; end < length; ++end) {
20            // Include the next element in the window and update its count.
21            count[nums[end] + 50]++;
22            // Exclude the element that is now outside the window and update its count.
23            count[nums[end - k] + 50]--;
24            // Calculate beauty for the new subarray and store it.
25            beautyValues[start++] = calculateBeauty(count, x);
26        }
27      
28        return beautyValues;
29    }
30
31    // Helper method to calculate beauty using the frequency count array and value x.
32    private int calculateBeauty(int[] count, int x) {
33        int sum = 0;
34        // Iterate over the count array to calculate cumulative sum.
35        for (int i = 0; i < 50; ++i) {
36            sum += count[i];
37            // If the cumulative sum is at least x, return the value representing beauty.
38            if (sum >= x) {
39                return i - 50; // Offset by 50 to get the actual value.
40            }
41        }
42        // If beauty couldn't be determined within loop range, return 0.
43        return 0;
44    }
45}
46

C++ Solution

1#include <vector>
2
3class Solution {
4public:
5    // Defines a method to calculate the subarray beauties for all subarrays of size k.
6    // A subarray's beauty is defined by the x-th smallest element in this subarray.
7    // nums: an integer vector
8    // k: the size of the subarrays
9    // x: the position of the element that defines the beauty
10    // Returns a vector with the beauty of each subarray
11    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
12        int n = nums.size(); // total number of elements in the input array
13        int counts[101] = {}; // an array to keep the count of elements (offset by 50 to handle negative numbers)
14
15        // Initialize the counts for the first subarray
16        for (int i = 0; i < k; ++i) {
17            ++counts[nums[i] + 50];
18        }
19
20        // Create a vector to store the answer
21        vector<int> beauties(n - k + 1);
22
23        // Lambda function to find the x-th smallest number in the current subarray
24        auto findXthSmallest = [&](int xth) {
25            int sum = 0;
26            for (int i = 0; i < 50; ++i) {
27                sum += counts[i];
28                if (sum >= xth) { // if the cumulative count hits xth, we found our xth smallest
29                    return i - 50; // return the number considering the offset
30                }
31            }
32            return 0; // placeholder, this case should not happen as sum should always hit xth before i reaches 50
33        };
34
35        // Calculate the beauty for the first subarray
36        beauties[0] = findXthSmallest(x);
37
38        // Calculate the beauty for remaining subarrays
39        for (int i = k, j = 1; i < n; ++i, ++j) {
40            ++counts[nums[i] + 50]; // include the new number in the count
41            --counts[nums[i - k] + 50]; // exclude the oldest number from the count
42            beauties[j] = findXthSmallest(x); // calculate the beauty for the current subarray
43        }
44
45        return beauties; // return the computed beauties
46    }
47};
48

Typescript Solution

1function getSubarrayBeauty(nums: number[], windowSize: number, beautyRank: number): number[] {
2    const numLength = nums.length;
3    // Initialize a count array to keep track of number frequencies within a window
4    const count = new Array(101).fill(0);
5  
6    // Populate the count for the initial window of size windowSize
7    for (let i = 0; i < windowSize; ++i) {
8        ++count[nums[i] + 50];
9    }
10
11    // Initialize an array to store the beauty of each subarray
12    const beautyArray: number[] = new Array(numLength - windowSize + 1);
13
14    // Helper function to calculate the beauty of the current window
15    const calculateBeauty = (rank: number): number => {
16        let sum = 0;
17        for (let i = 0; i < 50; ++i) {
18            sum += count[i];
19            if (sum >= rank) {
20                return i - 50;
21            }
22        }
23        return 0; // Default return if rank is never reached
24    };
25  
26    // Calculate the beauty for the first window
27    beautyArray[0] = calculateBeauty(beautyRank);
28
29    // Slide the window through the array and calculate the beauty of each subarray
30    for (let i = windowSize, j = 1; i < numLength; ++i, ++j) {
31        count[nums[i] + 50]++;
32        count[nums[i - windowSize] + 50]--;
33        beautyArray[j] = calculateBeauty(beautyRank);
34    }
35
36    // Return the array containing the beauty of each subarray
37    return beautyArray;
38}
39

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by several operations: initializing the SortedList, adding elements to it, removing elements from it, and looking up an element at a specific index within it.

  1. Initializing SortedList with nums[:k] takes O(k log(k)) time, as it needs to sort k elements.
  2. The for loop runs (n - k) times, where n is the length of nums.
  3. Inside the loop, sl.remove(nums[i - k]) takes O(log(k)) time as SortedList maintains the elements in sorted order, so removal is a logarithmic operation.
  4. sl.add(nums[i]) also takes O(log(k)) time for the same reason – to maintain the sorted property of the list.
  5. Accessing the x-1th smallest item with sl[x - 1] is an O(1) operation because SortedList allows for fast random access.

Combining these operations, the total time complexity for the loop is (n - k) * (2 * log(k)). So the overall time complexity of the code can be expressed as:

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

since k log(k) is insignificant compared to (n - k) * log(k) for large n.

Space Complexity

The space complexity is determined by the extra space used for the SortedList and the ans list.

  1. The SortedList at any time contains exactly k elements, giving a space complexity of O(k).
  2. The ans list will contain n - k + 1 elements (as we insert a new number for every element from nums[k] to nums[n-1]), so this also gives a space complexity of O(n).

Combining these, the dominant space complexity remains O(n) (as we typically consider the worst-case space usage to determine space complexity).

Therefore, the space complexity of the code is O(n).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫