Pattern this teaches:Monotonic Queue
Sliding Window Maximum
A hard Queue interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Queue
- Sheets
- 2
- Core for
- 10 roles
The problem
Given an array of integers and a sliding window of size k, return an array of the maximum value in each window as it slides from left to right.
Example 1
- Input
- nums = [4,2,12,-3,7,5,1,8], k = 3
- Output
- [12,12,12,7,7,8]
- Why
- Each window of three keeps its largest value: 12 dominates the first three windows, then 7, 7 and 8 take over.
Example 2
- Input
- nums = [1], k = 1
- Output
- [1]
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length
How to think about it
Updated 2026-09-29An element inside the window renders every earlier element smaller than itself permanently obsolete: they are smaller and will expire sooner, so none of them can ever be the window maximum again. Stripping those dead candidates leaves a decreasing sequence where the current maximum is always sitting at the front.
Approaches, worst first
Rescan each window
time O(n * k) · space O(1)
Step through each valid start index and find the maximum among the k elements by a linear scan. Simple to write, but it recalculates overlapping ranges from scratch and chokes when both n and k grow large.
Max-heap with lazy deletion
time O(n log n) · space O(n)
Store pairs of value and index in a priority queue. Pop invalid indices from the top when they fall behind the sliding left boundary. Avoids full rescans, but incurs logarithmic insertion and heap maintenance overhead.
Monotonic deque of indicesWrite this one
time O(n) · space O(k)
Maintain indices in a double-ended queue with strictly decreasing values. Evict the front index if it has slid out of range, then pop smaller values from the back before pushing the current index. Each index enters and exits the deque once.
Where people lose marks · 4
- Storing raw values instead of indices in the deque, making it impossible to check whether the current maximum has expired past the left boundary.
- Emitting window maximums before the first k elements have been processed, polluting the output with partial prefixes.
- Dropping equal values from the back using greater-than-or-equal instead of strict comparison, prematurely ejecting duplicate maximums that expire later.
- Off-by-one on boundary expiration: the index at i - k is expired, while i - k + 1 is still inside the active window.
The theory behind it
Queue — the ground this problem stands on. All Queue problems
What Queue is
A queue is an orderly checkout line at a grocery store counter where patrons enter at the back and leave from the front. The person who arrives first gets served first, while newcomers wait patiently behind whoever came before them. Unlike a stack which turns back on its latest arrival, a queue preserves fair chronological arrival order, processing tasks strictly from oldest to newest.
When to reach for it
Reach for a queue when exploring states level by level, such as finding the shortest path across an unweighted graph or traversing a tree horizontally. It fits rate-limiting buffers, print spools, asynchronous task schedulers, and sliding cache windows where oldest items expire first. Any problem stating that processing must honor strict time-of-arrival order is an immediate candidate.
How the pattern works
Track two distinct ends: an enqueue boundary at the tail and a dequeue boundary at the head. In breadth traversals, snapshot the queue size before starting an inner loop to process an entire depth tier in one grouped wave. Items currently enqueued represent the frontier of known but unresolved states. Ensure newly generated states are marked visited upon insertion rather than upon extraction to prevent duplicated queue entries.
More Queue problems
Target Roles
Core requirement for 10 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .