Sliding Window Maximum
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
For every window of size k sliding across the list, report the maximum value in the window.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Recomputing the max of every window is O(n x k). What can you reuse between neighbouring windows?
- Hint 2When a new value arrives, which earlier values in the window become useless?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A cricket team picks its "best player of the last 3 matches". When a new player scores higher than the ones recorded before him, those older weaker players can never again be the best, because the new star will stay in the last-3 list longer than they will. So you keep a short list of candidates in descending order of score: the front is always the best. Players who age out of the last 3 matches leave from the front.
- The obvious way
Find the maximum of each window directly: O(n x k).
- The key insight
Keep a deque of positions whose values are in decreasing order. For each new value, remove from the back every position with a smaller value (they can never be a maximum while the new one is around), then add the new position. Remove the front if it has slid out of the window. The front of the deque is always the window maximum. Each position enters and leaves once: O(n).
- The algorithm
- Empty deque of positions; empty answer list.
- For each position: pop from the BACK while its value is smaller than the new value.
- Add the new position at the back. If the FRONT position is out of the window, remove it.
- Once the first window is full, the front's value is that window's maximum: record it.
Watch it run
Examplenumbers = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Add 1, then 3: 3 is bigger than 1, so 1 can never be the best again. Candidates: [3].
candidates: 3
Where people slip
- Store positions, not values: you need the position to know when something leaves the window.
- A max-heap also works (O(n log n)) but needs lazy deletion of out-of-window items.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
from collections import deque
def max_sliding_window(nums, k):
candidates = deque() # positions, values in decreasing order
answer = []
for position, value in enumerate(nums):
while candidates and nums[candidates[-1]] < value:
candidates.pop() # older and smaller: never the maximum again
candidates.append(position)
if candidates[0] <= position - k: # the front slid out of the window
candidates.popleft()
if position >= k - 1:
answer.append(nums[candidates[0]]) # the front is the window maximum
return answerNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.