HardCoding

Sliding Window Maximum

Asked at

BharatPe

Cisco Meraki

HashedIn

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

Hiring now

LinkedIn has 196 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer - Systems and Infrastructure
Mountain View, CA, United States
Lead Account Executive, Large Customer, Financial Services - LinkedIn Marketing Solutions
Chicago, IL, United States
Director, LinkedIn Pulse Digital Platform
New York, NY, United States

Or practice this question first

Next question