Coding interview problems › Sliding Window

🪟 Sliding Window Hard

Sliding Window Maximum

Sliding Window Maximum explained: a monotonic deque of indices keeps the window max at the front, giving every window's maximum in O(n). Tested Python.

Also searched as: maximum of all subarrays of size k · monotonic deque sliding window maximum

🪟

Try it live Free

Sliding Window

Slide a fixed window across the array as elements enter and leave. Tracking the maximum needs one more idea from the monotonic stack: drop any waiting value the moment a bigger one arrives.

Also useful: Stacks & the Monotonic Stack

Open the playground →

The problem

Given a list of integers and a window size k, slide the window from left to right one step at a time and return the maximum of each window.

Inputnums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output[3, 3, 5, 5, 6, 7]

The key insight

Keep a deque of indices whose values are in decreasing order. When a new value arrives, pop every smaller value from the back: those can never be a maximum again, because the new value is both larger and will stay in the window longer. The front of the deque is always the current maximum; drop it once it slides out of the window.

Brute force first: Taking max() of every window is O(n·k); a heap gives O(n log n).

Step-by-step approach

  1. Create an empty deque dq of indices.
  2. For each index i: while the back of dq has a value <= nums[i], pop it.
  3. Append i.
  4. If the front index is <= i - k, it has left the window, so pop it from the front.
  5. Once i >= k - 1, append nums[dq[0]] to the answer.

Python solution

PYTHON 3tested
from collections import deque


def max_sliding_window(nums, k):
    dq, out = deque(), []          # indices, values decreasing
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()               # smaller values can never be max again
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()           # front slid out of the window
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Complexity

TimeO(n)
SpaceO(k)

Every index is appended once and popped at most once, so all deque work adds up to O(n). The deque never holds more than k indices.

Common mistakes

Frequently asked questions

What is the time and space complexity of Sliding Window Maximum?

The monotonic deque solution is O(n) time and O(k) space. A max-heap solution is O(n log n), and the brute force is O(n·k).

Why can smaller elements be removed from the deque for good?

A smaller element that arrived earlier will leave the window before the new larger one, so while it is in the window the larger one is always there to beat it.

How is this related to the monotonic stack?

It is the same pop-while-smaller rule as Next Greater Element. The deque adds one thing: removing expired indices from the front.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Sliding Window Sliding Window lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.