0% completed
Problem Statement
You are given an array of integers nums
, and integer k
, size of the sliding window which moves from the very left
to the very right
in the array. In each window, you can have only k
numbers, and the window moves one position right by each time.
Return the array containing the maximum element
of each sliding window.
Examples
Example 1:
- Input: nums = [2, 1, 5, 1, 3, 2], k = 3
- Expected Output: [5, 5, 5, 3]
- Justification: Here, the window of size 3 moves across the array. The maximum values in each window are 5 (from [2, 1, 5]), 5 (from [1, 5, 1]), 5 (from [5, 1, 3]), and 3 (from [1, 3, 2]).
Example 2:
- Input: nums = [4, -2, -3, 4, 1], k = 2
- Expected Output: [4, -2, 4, 4]
- Justification: The maximum values in each window of size 2 are 4 (from [4, -2]), -2 (from [-2, -3]), 4 (from [-3, 4]), and 4 (from [4, 1]).
Example 3:
- Input: nums = [9, 7, 2, 4, 6], k = 4
- Expected Output: [9, 7]
- Justification: In this case, there are only two windows of size 4. The maximum value in the first window is 9 (from [9, 7, 2, 4]), and in the second window is 7 (from [7, 2, 4, 6]).
Constraints:
- 1 <= nums.length <= 10<sup>5</sup>
- -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
- 1 <= k <= nums.length
Solution
To solve this problem, we'll use a deque (double-ended queue) to maintain the indices of the elements in the current window, ensuring the deque always has the maximum element's index at the front. This approach works because it allows us to efficiently remove elements that are no longer in the window (by checking if they are out of the current window's range) and ensure the first element in the deque is always the maximum of the current window. We'll iterate through the array, adding each element's index to the deque while maintaining these properties.
This method is effective because it combines the efficiency of a queue for managing the window's sliding mechanism with the ability to quickly update and retrieve the maximum value. By only storing relevant indices and removing those that are no longer in the window or are not potential maximums, we significantly reduce the time complexity compared to brute force methods that check every window's maximum separately.
Step-by-step Algorithm
- Initialize an empty deque
D
to store indices of array elements. - Iterate through each element of the array
nums
:- If
D
is not empty and the front element ofD
is out of the current window's range (i - k
), pop it from the front. - While
D
is not empty and the current element is greater than the element at the back ofD
, pop elements from the back. This ensures that the first element inD
is always the maximum of the current window. - Add the current index
i
to the back ofD
. - If
i
is greater than or equal tok - 1
, append the front element ofD
to the result array, as the window has now reached its full size.
- If
- Return the result array containing the maximums.
Algorithm Walkthrough
Let's consider the input: nums = [2, 1, 5, 1, 3, 2], k = 3
-
Initialization:
- The deque
D
is initialized as empty. - An empty result array is initialized to store the maximum of each window.
- The deque
-
Iteration 1 (i = 0, nums[i] = 2):
- Since
D
is empty, add index0
toD
. D
now contains[0]
.- The window has not yet reached its full size (
k = 3
), so we don't add anything to the result array.
- Since
-
Iteration 2 (i = 1, nums[i] = 1):
- No indices are removed from
D
since all indices inD
are within the current window's range. nums[i]
is less thannums[D.back()]
(1 < 2), so just add index1
toD
.D
now contains[0, 1]
.- The window has not reached its full size, so no action on the result array.
- No indices are removed from
-
Iteration 3 (i = 2, nums[i] = 5):
- No indices are removed from
D
for being out of range. nums[i]
is greater thannums[D.back()]
, so remove indices fromD
whilenums[i]
is greater thannums[D.back()]
. Remove0
and1
fromD
.- Add index
2
toD
sincenums[2]
is now the greatest so far. D
now contains[2]
.- The window has reached its full size. Add
nums[D.front()]
(which is5
) to the result array.
- No indices are removed from
-
Iteration 4 (i = 3, nums[i] = 1):
- No indices are removed from
D
for being out of range. nums[i]
is less thannums[D.back()]
, so just add index3
toD
.D
now contains[2, 3]
.- Add
nums[D.front()]
(which is still5
) to the result array since the window is full.
- No indices are removed from
-
Iteration 5 (i = 4, nums[i] = 3):
- No indices are removed from
D
for being out of range. nums[i]
is greater thannums[D.back()]
(the index atD.back()
is3
, andnums[3]
is1
), so remove index3
fromD
.- Add index
4
toD
. D
now contains[2, 4]
.- Add
nums[D.front()]
(which is5
) to the result array.
- No indices are removed from
-
Iteration 6 (i = 5, nums[i] = 2):
- Remove index
2
fromD
since it's out of the current window's range (i - k + 1 = 3
). nums[i]
is less thannums[D.back()]
, so just add index5
toD
.D
now contains[4, 5]
.- Add
nums[D.front()]
(which is3
) to the result array.
- Remove index
-
Final Result:
- The result array, which contains the maximum of each window, is
[5, 5, 5, 3]
.
- The result array, which contains the maximum of each window, is
Code
Complexity Analysis
Time Complexity
- O(N): Each element in the array is processed exactly twice - once when it's added to the deque and once when it's removed. This leads to a linear time complexity because the operations of adding to and removing from the deque (or its equivalent data structure) are O(1) operations.
Space Complexity
- O(N): In the worst-case scenario, the space complexity is O(N) due to the storage requirements of the result array, which contains at most N - k + 1 elements. The deque (or similar structure) itself will have at most k elements because it only stores elements from the current window. However, since k is a constant that does not scale with the input size N, the dominant term for space complexity is due to the output array, making it O(N).
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible