The O(n) Club: Sliding Window Maximum — Enjoy O(N) Glory, Deque-Style!
⚡ TL;DR
If you’re still brute-forcing the max of every window, please stop. Here’s the tragic way (and why you need to do better):
for (int i = 0; i <= nums.length - k; i++) { int max = Integer.MIN_VALUE; for (int j = i; j < i + k; j++) { max = Math.max(max, nums[j]); } result[i] = max; }That’s O(Nk) — you want O(N). Enter: the mighty deque.
🧠 How Devs Usually Mess This Up
What devs *think* will work: using max() on each window, or a heap/PriorityQueue. But removing stuff from heaps is like waiting for your food at a busy diner — slow and anxiety-inducing. Arrays and normal queues are even worse — you cannot efficiently kick out old values and keep track of who’s the biggest. The result: slow code, sad interviewers, no callback.
🔍 What’s Actually Going On
Picture your array as a line of people at the club (yes, again): the bouncer (deque) loves only the tallest and moves anyone who gets dwarfed or leaves the window. We store indices in this deque, so the bouncer knows who’s expired just by looking at their number. This keeps everything O(N) cool — every number gets in and out of the club once, no reruns. The tallest inside the window is always right up front.
🛠️ PseudoCode
- Start an empty deque for indices
- For every number in the array:
- Kick out indices if they’re outside the window (i – k + 1 and older)
- Pop indices from the back whose values are ≤ the current value (they can’t win)
- Add current index to the back
- Once window is full (i ≥ k – 1), max is at deque front
// Quick-and-dirty version
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
dq.offerLast(i);
if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
}
💻 The Code
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k <= 0) return new int[0];
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
deque.pollFirst();
}
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
⚠️ Pitfalls, Traps & Runtime Smacks
- Gotchas: Store indices, not numbers!
- k == 1? Every element is its own window — don’t overthink it.
- k == nums.length? The answer is just max of whole array — don’t overthink this either.
- Deque empty? You’re popping too much — go easy.
- Each value comes in, each goes out just once. That’s O(N) — not sorcery, just careful eviction.
🧠 Interviewer Brain-Tattoo
Deque: For when brute force is embarrassing and you want your code to enter production, not therapy. 💡
