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 x
th smallest integer in the subarray, but with a twist. If the x
th 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 x
th 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:
- We initialize
SortedList
with the firstk
elements of thenums
array. This automatically keeps these elements sorted. - We record the beauty of the initial subarray. The
x
th smallest element can be retrieved directly by indexx - 1
due to zero-based indexing. If this element is negative, it is the beauty; otherwise, we record0
. - 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.
- 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 x
th smallest element and compute the beauty without re-sorting the entire subarray each time.
Learn more about Sliding Window patterns.
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 x
th smallest number possible in constant time.
Let's walk through a detailed implementation strategy referencing the code provided:
-
We instantiate a
SortedList
with the firstk
elements of thenums
array. This prepares our first subarray and maintains its elements in sorted order.sl = SortedList(nums[:k])
-
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 listans
.ans = [sl[x - 1] if sl[x - 1] < 0 else 0]
-
Next, we enter a loop that iterates over
nums
from thek
th index to the end:for i in range(k, len(nums)):
- For each iteration, the leftmost (oldest) element of the previous subarray is removed from
SortedList
:
sl.remove(nums[i - k])
- Simultaneously, the next element in the array (
nums[i]
) is added toSortedList
, again maintaining sorting:
sl.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:
ans.append(sl[x - 1] if sl[x - 1] < 0 else 0)
- For each iteration, the leftmost (oldest) element of the previous subarray is removed from
-
Finally, after the loop completes,
ans
contains the beauty of each subarray. This result is then returned.return 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 = 2
nd smallest negative integer in the subarray.
-
Initialize a
SortedList
with the firstk
elements of thenums
array:sl = SortedList([-1, 2, -3])
The sorted list would be
[-3, -1, 2]
. -
Calculate the beauty of the first subarray:
ans = [-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
inans
.Now,
ans = [-1]
. -
Slide the window and update the
SortedList
:For the next subarray
[2, -3, 4]
, remove the element-1
fromsl
and add4
:sl.remove(-1) sl.add(4)
Now
sl
becomes[-3, 2, 4]
. The element at index1
is now2
, so the beauty of this subarray is0
.Update
ans
to include the new beauty:ans = [-1, 0]
. -
Move the window to the next subarray
[4, -5]
:Remove the leftmost element
2
fromsl
and add-5
:sl.remove(2) sl.add(-5)
The sorted list now is
[-5, -3, 4]
. The element at index1
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.
Solution Implementation
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
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
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
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.
- Initializing
SortedList
withnums[:k]
takes O(k log(k)) time, as it needs to sortk
elements. - The for loop runs (n - k) times, where
n
is the length ofnums
. - Inside the loop,
sl.remove(nums[i - k])
takes O(log(k)) time asSortedList
maintains the elements in sorted order, so removal is a logarithmic operation. sl.add(nums[i])
also takes O(log(k)) time for the same reason ā to maintain the sorted property of the list.- Accessing the
x-1
th smallest item withsl[x - 1]
is an O(1) operation becauseSortedList
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.
- The
SortedList
at any time contains exactlyk
elements, giving a space complexity of O(k). - The
ans
list will containn - k + 1
elements (as we insert a new number for every element fromnums[k]
tonums[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)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!