These are the notes for DSA episode 11, another hard classic. Sliding Window Maximum (LeetCode 239) asks for the biggest number in every window of k consecutive numbers. The brute force re-scans every window (O(n·k)), a single running maximum gives wrong answers, and the fix is a new data structure: the monotonic deque, which solves it in O(n) time. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
In episodes 9 and 10 the window grew and shrank. Here the window has a fixed size k, but the question is harder: a sum or a count can be updated in O(1) when one number leaves, a maximum cannot.
The problem, in real life
It is sports day trials for the school basketball team. The coach sits in the staffroom, and the kids walk past the window in a single line. The window shows exactly three kids at a time: every second, one kid walks into view on the right and one walks out on the left. Every second, the coach writes down the height of the tallest kid in view.
With three kids he just looks. With a thousand kids and a window showing five hundred, measuring all five hundred again every second is far too slow.
Problem statement
Given an array a of n integers and a window size k, return the maximum of every window of k consecutive numbers (there are n - k + 1 windows). Constraints: 1 ≤ n ≤ 10⁵, -10⁴ ≤ a[i] ≤ 10⁴, 1 ≤ k ≤ n.
| a | k | answer |
|---|---|---|
| [1, 3, -1, -3, 5, 3, 6, 7] | 3 | [3, 3, 5, 5, 6, 7] |
| [1, 3, -1, -3, 5, 3, 6, 7] | 1 | the array itself |
| [1, 3, -1, -3, 5, 3, 6, 7] | 8 | [7] |
| [9, 8, 7, 6, 5] | 2 | [9, 8, 7, 6] |
| [4, 4, 4, 4] | 3 | [4, 4] |
| [3, 3, 1] | 2 | [3, 3] |
The windows of the first example:
| Window | Numbers | Max |
|---|---|---|
| 0..2 | 1, 3, -1 | 3 |
| 1..3 | 3, -1, -3 | 3 |
| 2..4 | -1, -3, 5 | 5 |
| 3..5 | -3, 5, 3 | 5 |
| 4..6 | 5, 3, 6 | 6 |
| 5..7 | 3, 6, 7 | 7 |
Solution 1: brute force (re-scan every window)
import java.util.*;
public class Main {
static int[] maxWindow(int[] a, int k) {
int n = a.length;
int[] res = new int[n - k + 1];
for (int i = 0; i + k <= n; i++) {
int best = a[i];
for (int j = i; j < i + k; j++) best = Math.max(best, a[j]);
res[i] = best;
}
return res;
}
static void show(int[] a, int k) {
System.out.println(Arrays.toString(maxWindow(a, k)));
}
public static void main(String[] args) {
int[] a = {1, 3, -1, -3, 5, 3, 6, 7};
show(a, 3);
}
}
Output:
[3, 3, 5, 5, 6, 7]
Now ten lakh numbers with a window of five lakh:
int n = 1000000, k = 500000, a[] = new int[n];
for (int i = 0; i < n; i++) a[i] = (int) (i * 7919L % 1000003);
long t = System.nanoTime();
int[] res = maxWindow(a, k);
long ms = (System.nanoTime() - t) / 1000000;
System.out.println(res.length + " windows, last max " + res[n - k]);
System.out.println(ms + " ms");
Result: Time Limit Exceeded.
Why it is slow
- There are
n - k + 1windows and each scansknumbers: O(n·k). - With
k = n/2that is aboutn²/4: forn = 10⁶, about 2.5 × 10¹¹ steps. - Neighbouring windows share
k - 1numbers. Only one number leaves and one comes in, yet we re-measure everything.
The obvious fix that breaks: one running maximum
Keep one variable best, update it with every new number, and write it out once the first window is full:
static int[] maxWindow(int[] a, int k) {
int n = a.length;
int[] res = new int[n - k + 1];
int best = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
best = Math.max(best, a[i]);
if (i >= k - 1) res[i - k + 1] = best;
}
return res;
}
With show(a, 3) and show(new int[]{9, 8, 7, 6, 5}, 2):
[3, 3, 5, 5, 6, 7]
[9, 9, 9, 9]
The first answer is right by luck. The second is wrong: the 9 left the window after the first step, but the variable still remembers it. When the maximum leaves, one variable cannot tell us who is next. We need the runner-up, and the one after that: a list of candidates. But keeping all k numbers is the brute force again. Which numbers can ever be a maximum?
The key insight: useless numbers
A tall kid walks into view. Every shorter kid standing ahead of him can never be the tallest in view again: they walked in earlier, so they walk out earlier, and while they are in view he is in view too. The coach can forget them immediately.
In code: a smaller number that comes before a bigger number is useless. So keep only the candidates:
- Their values are always decreasing from front to back (that is what monotonic means: always going one way).
- A new number pops every smaller number off the back, then goes in at the back.
- When the number at the front falls out of the window, pop it off the front.
- The front is always the maximum of the current window.
Removing from both ends needs a deque (double-ended queue). Java's ArrayDeque adds and removes at both ends in O(1).
Store indices, not values: the index tells you exactly when a number has left the window (index ≤ i - k), and it keeps equal values apart.
Dry run: a = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Each step: (1) expire the front if front ≤ i - k, (2) pop smaller values from the back, (3) push i, (4) once i ≥ k - 1, the answer is a[front].
| i | a[i] | What happens | Deque (indices) | Values | Window max |
|---|---|---|---|---|---|
| 0 | 1 | push 0 | [0] | 1 | |
| 1 | 3 | 3 > 1: pop 0, push 1 | [1] | 3 | |
| 2 | -1 | smaller, push | [1, 2] | 3, -1 | 3 |
| 3 | -3 | front 1 > 0 stays, push | [1, 2, 3] | 3, -1, -3 | 3 |
| 4 | 5 | front 1 ≤ 1 expires; 5 pops 3 and 2 | [4] | 5 | 5 |
| 5 | 3 | smaller, push | [4, 5] | 5, 3 | 5 |
| 6 | 6 | pops 5 and 4 | [6] | 6 | 6 |
| 7 | 7 | pops 6 | [7] | 7 | 7 |
Answer: [3, 3, 5, 5, 6, 7].
Solution 2: the monotonic deque, O(n)
import java.util.*;
public class Main {
static int[] maxWindow(int[] a, int k) {
int n = a.length;
int[] res = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
while (!dq.isEmpty() && a[dq.peekLast()] < a[i]) dq.pollLast();
dq.offerLast(i);
if (i >= k - 1) res[i - k + 1] = a[dq.peekFirst()];
}
return res;
}
static void show(int[] a, int k) {
System.out.println(Arrays.toString(maxWindow(a, k)));
}
public static void main(String[] args) {
int[] a = {1, 3, -1, -3, 5, 3, 6, 7};
show(a, 3);
show(a, 1);
show(a, 8);
show(new int[]{9, 8, 7, 6, 5}, 2);
show(new int[]{4, 4, 4, 4}, 3);
}
}
Output:
[3, 3, 5, 5, 6, 7]
[1, 3, -1, -3, 5, 3, 6, 7]
[7]
[9, 8, 7, 6]
[4, 4]
Edge cases covered: k = 1 (every number is its own window), k = n (one window), a decreasing array (nothing is popped from the back, so front expiry does all the work), and all-equal values.
On ten lakh numbers with k = 5 × 10⁵ (time varies from run to run):
500001 windows, last max 1000001
163 ms
Why it is O(n): amortized analysis
There is a while loop inside the for loop, but count per index, not per step:
- every index is pushed exactly once;
- once popped (from the back or the front) it is gone, so it is popped at most once.
So all the while loops together pop at most n times, and pushes + pops ≤ 2n: O(n) in total. A single step can pop many numbers, but those numbers are then gone and later steps pop nothing; on average each step is O(1). That is amortized O(1) per step.
Space: the deque never holds more than k indices (older ones expire), so O(k) extra, plus the output.
The same solution in C++ and Python
C++ (std::deque):
#include <bits/stdc++.h>
using namespace std;
vector<int> maxWindow(const vector<int>& a, int k) {
int n = a.size();
if (k > n) return {};
vector<int> res;
deque<int> dq; // indices, values decreasing
for (int i = 0; i < n; i++) {
if (!dq.empty() && dq.front() <= i - k) dq.pop_front();
while (!dq.empty() && a[dq.back()] < a[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) res.push_back(a[dq.front()]);
}
return res;
}
int main() {
vector<int> a = {1, 3, -1, -3, 5, 3, 6, 7};
for (int k : {3, 1, 8}) {
for (int x : maxWindow(a, k)) cout << x << ' ';
cout << '\n';
}
for (int x : maxWindow({9, 8, 7, 6, 5}, 2)) cout << x << ' ';
cout << '\n';
for (int x : maxWindow({3, 3, 1}, 2)) cout << x << ' ';
cout << '\n';
}
Output:
3 3 5 5 6 7
1 3 -1 -3 5 3 6 7
7
9 8 7 6
3 3
Python (collections.deque):
from collections import deque
def max_window(a, k):
if k > len(a):
return []
dq, res = deque(), [] # indices, values decreasing
for i, x in enumerate(a):
if dq and dq[0] <= i - k:
dq.popleft()
while dq and a[dq[-1]] < x:
dq.pop()
dq.append(i)
if i >= k - 1:
res.append(a[dq[0]])
return res
a = [1, 3, -1, -3, 5, 3, 6, 7]
print(max_window(a, 3))
print(max_window(a, 1))
print(max_window(a, 8))
print(max_window([9, 8, 7, 6, 5], 2))
print(max_window([3, 3, 1], 2))
print(max_window([1, 2], 4))
Output:
[3, 3, 5, 5, 6, 7]
[1, 3, -1, -3, 5, 3, 6, 7]
[7]
[9, 8, 7, 6]
[3, 3]
[]
The middle solution: a max-heap with lazy deletion, O(n log k)
A max-heap (PriorityQueue with a reversed comparator) always gives the biggest value. Store {value, index} pairs. We cannot cheaply delete the number that leaves the window, so we delete lazily: only when an expired pair reaches the top.
import java.util.*;
public class Main {
static int[] maxWindow(int[] a, int k) {
int n = a.length;
int[] res = new int[n - k + 1];
// max-heap of {value, index}; bigger value first
PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> Integer.compare(y[0], x[0]));
for (int i = 0; i < n; i++) {
pq.offer(new int[]{a[i], i});
while (pq.peek()[1] <= i - k) pq.poll(); // lazy deletion
if (i >= k - 1) res[i - k + 1] = pq.peek()[0];
}
return res;
}
public static void main(String[] args) {
int[] a = {1, 3, -1, -3, 5, 3, 6, 7};
System.out.println(Arrays.toString(maxWindow(a, 3)));
System.out.println(Arrays.toString(maxWindow(new int[]{9, 8, 7, 6, 5}, 2)));
int n = 1000000, k = 500000, b[] = new int[n];
for (int i = 0; i < n; i++) b[i] = (int) (i * 7919L % 1000003);
long t = System.nanoTime();
int[] res = maxWindow(b, k);
System.out.println(res.length + " windows, last max " + res[n - k]
+ " " + (System.nanoTime() - t) / 1000000 + " ms");
}
}
Output:
[3, 3, 5, 5, 6, 7]
[9, 8, 7, 6]
500001 windows, last max 1000001 176 ms
Fast enough, but the heap can hold up to n pairs (expired ones wait until they reach the top), so it is O(n log n) in the worst case and O(n) space. The deque is simpler and strictly linear.
Complexity
| Approach | Time | Extra space | n = 10⁶, k = 5 × 10⁵ |
|---|---|---|---|
| Brute force (re-scan every window) | O(n·k) | O(1) | Time Limit Exceeded (≈ 2.5 × 10¹¹ steps) |
| One running max | O(n) | O(1) | fast but wrong |
| Max-heap, lazy deletion | O(n log n) worst | O(n) | ~180 ms |
| Monotonic deque | O(n) amortized | O(k) | ~160 ms (≤ 2 × 10⁶ pushes + pops) |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| One running max variable | [9, 9, 9, 9] for {9, 8, 7, 6, 5}, k = 2 (answer [9, 8, 7, 6]) |
the max left the window but is still remembered | keep a deque of candidates |
Values in the deque, expiring with dq.peekFirst() == a[i - k] |
[3, 1] for {3, 3, 1}, k = 2 (answer [3, 3]) |
equal values can't be told apart: the wrong 3 is thrown out | store indices and expire with front <= i - k |
| No front expiry | [9, 9, 9, 9] for {9, 8, 7, 6, 5}, k = 2 |
the old maximum never leaves the deque | if (front <= i - k) pollFirst() |
k > a.length |
Exception in thread "main" java.lang.NegativeArraySizeException: -1 |
n - k + 1 is negative |
if (k > a.length) return new int[0]; |
| Popping from the front instead of the back for smaller values | wrong answers | the newest numbers are at the back | pollLast() while a[back] < a[i] |
Heap comparator y[0] - x[0] on large values |
wrong order | subtraction can overflow | Integer.compare(y[0], x[0]) |
The values-instead-of-indices bug, run live:
for (int i = 0; i < n; i++) {
if (i >= k && dq.peekFirst() == a[i - k]) dq.pollFirst();
while (!dq.isEmpty() && dq.peekLast() <= a[i]) dq.pollLast();
dq.offerLast(a[i]);
if (i >= k - 1) res[i - k + 1] = dq.peekFirst();
}
With show(a, 3) and show(new int[]{3, 3, 1}, 2):
[3, 3, 5, 5, 6, 7]
[3, 1]
The second 3 popped the first 3 (fine). When the first 3 left the window, the check saw a 3 at the front and threw out the second 3, which was still inside. The index version prints [3, 3].
The k > n crash, with show(new int[]{1, 2}, 4):
Exception in thread "main" java.lang.NegativeArraySizeException: -1
at Main.maxWindow(Main.java:5)
at Main.show(Main.java:16)
at Main.main(Main.java:19)
With the guard line if (k > a.length) return new int[0]; it prints [].
Mini project: watch the deque
Print the deque after every step, so you can see candidates arrive, get popped and expire:
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] a = {2, 7, 3, 1, 5, 4};
int k = 3;
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < a.length; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
while (!dq.isEmpty() && a[dq.peekLast()] < a[i]) dq.pollLast();
dq.offerLast(i);
String max = i >= k - 1 ? " max " + a[dq.peekFirst()] : "";
System.out.println("i = " + i + " deque " + dq + max);
}
}
}
Output:
i = 0 deque [0]
i = 1 deque [1]
i = 2 deque [1, 2] max 7
i = 3 deque [1, 2, 3] max 7
i = 4 deque [4] max 5
i = 5 deque [4, 5] max 5
Extend it: print the values next to the indices, and mark which indices were popped from the back and which expired from the front.
Practice
- Sliding window minimum. Return the minimum of every window.
Solution
Flip one comparison: pop from the back while a[back] > a[i], so values increase from front to back and the front is the minimum.
while (!dq.isEmpty() && a[dq.peekLast()] > a[i]) dq.pollLast(); // only this sign changes
For {1, 3, -1, -3, 5, 3, 6, 7}, k = 3 it prints [-1, -3, -3, -3, 3, 3].
- Without running code, write the window maxima of
{2, 7, 3, 1, 5, 4}with k = 3.
Solution
Windows 2,7,3, 7,3,1, 3,1,5, 1,5,4: [7, 7, 5, 5].
- Should the back-pop use
<or<=?
Solution
Both give correct maxima with indices. < keeps equal values (the deque is non-increasing), <= drops the older equal value (strictly decreasing, slightly smaller deque). With values instead of indices, <= plus value-based expiry is exactly the [3, 1] bug.
- Shortest subarray with sum at least K (LeetCode 862, hard), where numbers can be negative.
Solution
Take prefix sums p. Keep a deque of indices with increasing p. For each j: while p[j] - p[front] ≥ K, record j - front and pop the front (it can't give a shorter answer later). Then pop the back while p[back] ≥ p[j] (a larger, older prefix is useless), and push j. O(n).
Quick quiz
For a = {2, 7, 3, 1, 5, 4} and k = 3, which indices are in the deque right after processing i = 4 (the value 5)?
- [4]
- [1, 4]
- [2, 3, 4]
- [1, 2, 3, 4]
Answer
[4]. Before i = 4 the deque is [1, 2, 3] (values 7, 3, 1). Index 1 ≤ 4 - 3, so the 7 expires from the front. Then 5 pops index 3 (value 1) and index 2 (value 3) from the back. Only index 4 is left (see the mini project output).
Interview questions
- Why can't you keep a single running maximum? When the maximum leaves the window you don't know the next one; you need the candidates after it.
- Which numbers does the deque throw away, and why is that safe? Any number with a bigger number after it inside the window: it leaves earlier and is never bigger, so it can never be a window maximum.
- Why store indices instead of values? The index says when the number leaves (
index ≤ i - k) and keeps equal values apart. - There is a nested loop. Why is it O(n)? Each index is pushed once and popped at most once: at most 2n deque operations in total (amortized O(1) per step).
- How else could you solve it? A max-heap with lazy deletion (O(n log n)), or block-wise prefix/suffix maxima (split into blocks of size k; window max = max(suffixMax[i], prefixMax[i + k - 1]), O(n) with two arrays).
- Where else does a monotonic deque appear? Sliding window minimum, shortest subarray with sum ≥ K, jump game VI, constrained subsequence sum, and DP optimisations.
Glossary
| Term | Meaning |
|---|---|
| Window | A block of consecutive elements, here always k long |
| Sliding window (fixed size) | The window moves one step right: one element enters, one leaves |
| Window maximum | The largest element inside the current window |
| Brute force | The direct method: re-scan every window, O(n·k) |
| Running maximum | One variable holding the biggest value seen so far; it can't "forget" a value that left |
| Candidate | An element that could still be the maximum of a future window |
| Deque | Double-ended queue: add and remove at both the front and the back in O(1) |
ArrayDeque |
Java's resizable-array deque: offerLast, pollLast, peekLast, pollFirst, peekFirst |
| Monotonic | Always moving in one direction, never going back (here: values decreasing from front to back) |
| Monotonic deque | A deque whose values stay sorted because smaller ones are popped before a bigger one is pushed |
| Expire | Remove the front index when it is outside the window: front ≤ i - k |
| Amortized analysis | Counting total work over the whole run and averaging it: some steps are expensive, but the total is bounded |
| Max-heap | A tree-based structure that gives the largest element in O(1) and inserts/removes in O(log n) |
| Lazy deletion | Leaving stale elements in a heap and discarding them only when they reach the top |
NegativeArraySizeException |
Java's runtime error when you create an array with a negative size |
Summary
- Brute force re-scans every window: O(n·k), Time Limit Exceeded at n = 10⁶.
- One running max is fast but wrong: it can't recover when the max leaves.
- A smaller number before a bigger one is useless, so keep only candidates in a deque, values decreasing; the front is the maximum.
- Store indices; expire the front when
front ≤ i - k; pop smaller values from the back; pushi. - Every index goes in once and out once: O(n) time (amortized), O(k) extra space.
- Guard
k > nto avoidNegativeArraySizeException.
Next episode: Binary search: one template, first and last occurrence.