Skip to main content
Advanced

Sliding Window Maximum

hardHeaps (hard) Must-doGoogleUberDatadog

Problem statement

You're given an array of integers, nums, and a window of size k that slides across it one position at a time, from the very start to the very end. At each position, you can only see the k numbers currently inside the window. Return the maximum value inside the window at every position it stops at, in order.

Think of nums as a stream of readings — CPU load samples taken once a second, say — and k as a rolling window of the last k seconds. The output is the rolling maximum: the worst reading in the last k seconds, at every second.

Examples

Example 1

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

Output: [3,3,5,5,6,7]

Explanation: The window starts at [1,3,-1] (max 3), then slides to [3,-1,-3] (max 3), then [-1,-3,5] (max 5), then [-3,5,3] (max 5), then [5,3,6] (max 6), then finally [3,6,7] (max 7) — six window positions in total for an array of length 8 with k=3.

Example 2

Input: nums = [1], k = 1

Output: [1]

Explanation: With k equal to the whole array's length, there's only one window position, and its maximum is the single value itself.

Hints

Hint 1: Checking every value inside every window works, but neighbouring windows overlap heavily — most of the numbers you just looked at are still in the next window too.

Approach

Optimal: Monotonic deque

Intuition

The heap approach's real waste is that it keeps every value ever seen, even ones that can never possibly be a future maximum. If a smaller value sits behind a bigger, more recent value, that smaller value is permanently irrelevant — it will always lose to the bigger one for as long as the bigger one is still in range, and once the bigger one also leaves the window, the smaller one has already left too. So don't keep it at all: use a deque of indices, kept in strictly decreasing order of value (front-to-back). Before adding a new index, pop off the back of the deque any indices whose value is less than or equal to the new one — they're now provably useless. Also drop the front of the deque if its index has fallen out of the current window. The front of the deque is then always the current window's maximum, with no need to search or clean up beyond that.

Steps

  1. Keep a deque of indices, dq, kept so that nums at those indices is strictly decreasing from front to back.
  2. For each index i: while the deque isn't empty and the value at its back is less than or equal to nums[i], pop it from the back — it can never be a maximum again while nums[i] is still around.
  3. Push i onto the back of the deque.
  4. If the index at the front of the deque has fallen out of the window (it's <= i - k), pop it from the front.
  5. Once i >= k - 1 (the window is fully filled), the value at the front of the deque is the current window's maximum — append it to the result.

Dry run

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

i value pop from back while ≤ value dq after push pop expired front? window max (once i ≥ 2)
0 1 (empty) [0] — —
1 3 pop 0 (nums[0]=1 ≤ 3) [1] — —
2 -1 (nums[1]=3 > -1, stop) [1, 2] front 1 ≤ 2-3=-1? no nums[1] = 3
3 -3 (nums[2]=-1 > -3, stop) [1, 2, 3] front 1 ≤ 3-3=0? no nums[1] = 3
4 5 pop 3, pop 2, pop 1 (all ≤ 5) [4] front 4 ≤ 4-3=1? no nums[4] = 5
5 3 (nums[4]=5 > 3, stop) [4, 5] front 4 ≤ 5-3=2? no nums[4] = 5
6 6 pop 5, pop 4 (both ≤ 6) [6] front 6 ≤ 6-3=3? no nums[6] = 6
7 7 pop 6 (nums[6]=6 ≤ 7) [7] front 7 ≤ 7-3=4? no nums[7] = 7

Final result across the recorded window maxes: [3, 3, 5, 5, 6, 7] — matching both earlier approaches, with the deque never holding more than 3 indices at once.

Edge cases: when k equals the array's length (example 2), the deque simply accumulates indices (popping smaller ones as bigger ones arrive) until the single window position is reached, and the front is read exactly once. The front-expiry check (dq[0] <= i - k) only ever needs to remove at most one stale index per step, since the window only advances by one position at a time.

Complexity

Time O(n) - every index is pushed onto the deque at most once and popped from it at most once, from either end, across the entire run.

Space O(k) - the deque never holds more than k indices at a time, since it's kept trimmed to the current window's range.

from collections import deque
from typing import List


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()  # stores indices; values at those indices are decreasing
        result = []
        for i, num in enumerate(nums):
            # Drop indices whose value can never be the max while num is around.
            while dq and nums[dq[-1]] <= num:
                dq.pop()
            dq.append(i)
            # Drop the front if it has fallen out of the current window.
            if dq[0] <= i - k:
                dq.popleft()
            if i >= k - 1:
                result.append(nums[dq[0]])
        return result


if __name__ == "__main__":
    print(Solution().maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3))
    print(Solution().maxSlidingWindow([1], 1))
RecapThe whole problem in a few lines, for the night before
  • Spot it: the maximum of every window of size k as it slides across an array
  • Idea: keep a deque of indices whose values are in decreasing order; the front is always the current maximum
  • Cost: O(n) time, O(k) space, because each index enters and leaves the deque once
  • Trap: storing values instead of indices, so you can't tell when the front has slid out of the window

Interview follow-ups

  • What if you needed the rolling *minimum* instead of the maximum?

    Flip the comparison in the deque's cleanup step: instead of popping values that are less than or equal to the new one, pop values that are greater than or equal to it, keeping the deque increasing from front to back instead of decreasing. Everything else about the algorithm — the window expiry check, the O(n) time bound — stays exactly the same.

  • The readings arrive as a live stream rather than a fixed array, and you need the current window's maximum available at every moment, not just at the end.

    The same monotonic deque works directly in a streaming setting: each new reading triggers the same back-cleanup and front-expiry steps, and the front of the deque is always readable as "the current maximum" at any instant, without needing to know how many more readings are still to come. The only change from the array version is that there's no upfront n to loop over — the same per-reading logic just runs indefinitely as new values arrive.

Frequently asked questions

A value that's smaller than the newly arriving value, and appeared earlier in the array, is doomed the moment the bigger value shows up: as long as the bigger value is still inside the window, it will always beat the smaller one for "current maximum". By the time the bigger value eventually slides out of the window, the smaller value — which arrived even earlier — has already slid out too. So there's no future moment where the smaller value could win; discarding it early is always safe.

The front of the deque has to be checked for expiry — "has this entry's position fallen out of the current window?" — and that check needs to know where a value came from, not just what it was. Two equal values at different positions would be indistinguishable if only values were stored, making it impossible to tell which one (if either) has expired.

The heap discards entries lazily, only once they happen to bubble to the top — until then, they sit inside the heap taking up space and adding to every future push/pop's O(log n) cost, since the heap's size (and thus its depth) is affected by how many stale entries are still sitting inside it. The deque, by contrast, throws away useless entries immediately and permanently the moment a bigger value arrives, so it never carries dead weight — its size never exceeds k, keeping every operation to O(1) amortized instead of O(log n).

A rolling maximum over a moving window is exactly a moving-window alert threshold: the worst reading in the last k data points for CPU load, queue depth, or latency, recomputed efficiently as each new reading comes in rather than rescanning the whole window from scratch every time.