HardCoding

Sliding Window Maximum

Asked at

BharatPe

Cisco MerakiHHashedIn

Meta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an array of integers arr, there is a sliding window of size** k** which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Input: arr = [4, 0, -1, 3, 5, 3, 6, 8], k = 3 Output: [4, 3, 5, 5, 6, 8] Explanation:

For each window of size k=3, we find the maximum element in the window and add it to our output array.

Input: arr = [20, 25], k = 2 Output: [25] Explanation: There’s just one window of size 2 that is possible and the maximum of the two elements is our answer.

Input: arr = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

1 <= arr.length <= 105
-104 <= arr[i] <= 104
1 <= k <= arr.length

cpp

class Solution{
public:
    vector<int> maxSlidingWindow(vector<int> &arr, int k) {
        
    }
};

java

class Solution {
    public int[] maxSlidingWindow(int[] arr, int k) {
    
    }
}

python

class Solution:
    def maxSlidingWindow(self, arr, k):

javascript

class Solution {
    maxSlidingWindow(arr, k) {
   
    }
}

csharp

public class Solution
{
    public List<int> MaxSlidingWindow(List<int> arr, int k)
    {
        
    }
}

func maxSlidingWindow(arr []int, k int) []int {

}

Solve on LeetCode →

Stuck? Show a way to structure it+

01Store indices in a deque so expired elements can be recognized.
02Before inserting i, remove indices outside the window from the front.
03Remove smaller or equal values from the back because they can never become a future maximum.
04After the first k elements, read each window maximum from the deque front.

Reference answer

Maintain a deque of indices whose values are in decreasing order. The front is therefore the index of the maximum value in the current window.

For each index i, first remove the front while it is outside the window, meaning deque.front <= i - k. Then remove indices from the back while arr[deque.back] <= arr[i]. Those values are no larger than the new value and expire earlier, so they can never be the maximum of any future window containing i. Append i. Once i >= k - 1, append arr[deque.front] to the answer.

Store indices rather than values because expiry depends on position. Using <= when removing from the back keeps the newest copy of an equal value, which lasts longer; using < is also correct if expiry is handled carefully.

Each index enters and leaves the deque at most once, so the amortized time is O(n). The deque uses O(k) space. A heap solution is O(n log k) and must lazily remove expired entries.

Then expect these follow-ups

Why is each element removed from the deque at most once?
Tests: amortized analysis
How would you compute the sliding-window minimum as well?
Tests: pattern transfer

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question