Sliding Window Maximum (Two Pointers)
A hard Sliding Window interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Sliding Window
- Sheets
- 2
- Core for
- 6 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 that enters the window is both newer and potentially larger than older entries. Whenever a new number exceeds earlier numbers currently in the span, those older values can never serve as the window maximum again. Keeping only candidates in strictly descending order sheds useless values immediately and keeps the current leader at the front.
Approaches, worst first
Scan each span
time O(n * k) · space O(1)
Recompute the maximum across all k slots for every starting position. Simple to write, but completely ignores the k - 1 elements shared between adjacent windows.
Max-heap with indices
time O(n log n) · space O(n)
Store value-index pairs in a priority queue and discard the top whenever its index falls outside the current window. Correct, but pays a logarithmic penalty on every insertion and eviction.
Monotonic deque of indicesWrite this one
time O(n) · space O(k)
Maintain indices in a double-ended queue where values stay strictly decreasing. Pop smaller items from the back before inserting, drop expired indices from the front, and read the front as the window maximum. Each index enters and leaves at most once.
Where people lose marks · 3
- Storing raw values in the deque instead of their indices makes it impossible to tell whether the front element has expired past the left boundary.
- Popping from the back using greater-or-equal instead of strictly greater allows duplicate maximum values to survive, breaking strict monotonicity.
- Emitting maximums before the first k elements have been ingested adds garbage outputs for incomplete initial windows.
The theory behind it
Sliding Window — the ground this problem stands on. All Sliding Window problems
What Sliding Window is
A sliding window is an adjustable magnifying lens placed over a continuous segment of a sequence. Rather than recalculating metrics for every potential subsection from scratch, the window expands rightward by absorbing fresh elements and contracts leftward to expel stale entries. Only data currently framed within the window borders contributes to the active calculation.
When to reach for it
Reach for a sliding window when a question asks for the longest, shortest, or optimal contiguous subarray or substring matching a constraint. Key signals include fixed window sizes like maximum sum across k consecutive values, or dynamic criteria like finding the shortest substring holding all target characters. If the target subset must form an unbroken continuous run, window mechanics replace repetitive segment rescanning.
How the pattern works
Maintain two boundary indices, left and right, defining the active interval alongside a running state accumulator. In each step, expand the right boundary to incorporate the incoming element into state totals. When current state violates the designated problem constraints, increment the left boundary while deducting departing values until validity is restored. Update your tracking metric, whether minimum window length or maximum score, only during valid intervals.
More Sliding Window problems
Target Roles
Core requirement for 6 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 .