#239 Sliding Window Maximum
the problem
In plain words
A window of size k slides from the left of nums to the right, one step at a time. Return the maximum of each window.
in nums = [1,3,-1,-3,5,3,6,7], k = 3
out [3,3,5,5,6,7]
in nums = [1], k = 1
out [1]
- 1 ≤ n ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
- 1 ≤ k ≤ n
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternMonotonic dequeSliding window (fixed size)
If a newer element is ≥ an older one, the older one can never be a maximum again — it leaves the window first and is no bigger. Throw it away. What remains is a decreasing deque whose front is the max.
solutions
From brute force to optimal
For every start, scan k elements for the max.
- For start in 0..n−k: max over nums[start..start+k−1].
n − k + 1 windows × k elements — up to ~2.5·10⁹ steps at the limits.
Besides the output.
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] result = new int[n - k + 1]; for (int start = 0; start + k <= n; start++) { int best = Integer.MIN_VALUE; for (int j = start; j < start + k; j++) best = Math.max(best, nums[j]); // rescan the window result[start] = best; } return result; }}Keep {value, index} in a max-heap; before reading the top, pop entries whose index left the window.
- Offer {nums[i], i}.
- Once i ≥ k − 1: pop tops with index ≤ i − k.
- Record the top's value.
n offers and at most n polls, each O(log n).
Stale entries stay until they reach the top.
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] result = new int[n - k + 1]; // {value, index}, largest value on top PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0])); for (int i = 0; i < n; i++) { heap.offer(new int[] {nums[i], i}); if (i >= k - 1) { while (heap.peek()[1] <= i - k) heap.poll(); // lazily drop tops that left the window result[i - k + 1] = heap.peek()[0]; } } return result; }}Keep indices whose values decrease front → back. Evict the front when it leaves the window; pop smaller values from the back before pushing.
- If the front index ≤ i − k, poll it from the front.
- While the back value ≤ nums[i], poll from the back.
- Offer i at the back.
- Once i ≥ k − 1, record nums[front].
Each index is offered once and polled at most once.
The deque only holds indices inside the window.
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] result = new int[n - k + 1]; Deque<Integer> dq = new ArrayDeque<>(); // indices; values strictly decrease front → back for (int i = 0; i < n; i++) { if (!dq.isEmpty() && dq.peekFirst() <= i - k) { dq.pollFirst(); // the front index slid out of the window } while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) { dq.pollLast(); // smaller and older: can never be a max again } dq.offerLast(i); if (i >= k - 1) { result[i - k + 1] = nums[dq.peekFirst()]; // the front is the window max } } return result; }}Dry run
in the room
How to say it in the interview
talk track
- Brute force first (O(nk)), then: "a heap gets O(n log n), but we can do O(n) with a monotonic deque."
- State the invariant before coding: indices in the window, values strictly decreasing.
- Justify O(n) by counting pushes and pops, not loop nesting.
traps
- Storing values instead of indices — you lose the ability to expire the front.
- Evicting with
< i − kinstead of<= i − k(off-by-one keeps a stale max). - Popping the back with
<instead of<=still works, but keeps useless equal values;<=keeps the deque smaller.
what they ask next
Follow-ups
Sliding window minimum?
Same code with the comparison flipped: keep values increasing.
Longest subarray where max − min ≤ limit (LC 1438)?
Two monotonic deques (one for max, one for min) plus a variable-size window.
Where else does the monotonic deque appear?
Shortest Subarray with Sum at Least K (LC 862, below), Constrained Subsequence Sum (LC 1425), Jump Game VI (LC 1696) — DP optimised by a window max.
before you submit
Edge cases to test
- k = 1: the answer is the array itself.
- k = n: one window, one maximum.
- Strictly decreasing input: nothing is popped from the back, so the front must expire by its index.
- Equal values: popping with
<=keeps the deque small and the answer still correct.
practise next
Similar problems
- #862Shortest Subarray with Sum at Least KHardin Queues
- #739Daily TemperaturesMediumin Stacks
- #643Maximum Average Subarray IEasyin Sliding Window