Definition
- Sliding Window Maximum – return the maximum of every contiguous window of size K as the window slides across an array.
- Monotonic deque – a double-ended queue of indices maintained so the values at those indices are strictly decreasing from front to back.
- Back eviction – before adding a new index, pop from the back every index whose value is less than or equal to the new value.
- Front eviction – remove the front index if it has slid out of the window.
- Complexity – O(n) total time and O(K) space because each index enters and leaves the deque at most once.
The National Bank of India tracks a rolling K-minute peak of transaction rates. Rajesh keeps a short queue of candidate peak times, always ordered so the biggest is at the front. When a new, larger rate arrives, it knocks out every smaller candidate behind it. When a candidate falls out of the time window, it is removed from the front.
Understanding the Concepts
What is the Sliding Window Maximum problem?
Given an array of integers and a window size K, return an array where each element is the maximum of the contiguous window of K elements ending at that position (once the window is fully formed). The window slides from left to right one position at a time.
package com.bank.service;
import java.util.ArrayDeque;
import java.util.Deque;
public class SlidingWindowMaximum {
public static int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) return new int[0];
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>(); // stores indices
for (int i = 0; i < n; i++) {
// Remove from back: smaller values are now useless
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
// Remove from front: index out of window
if (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
// Record the maximum once window is full
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
public static void main(String[] args) {
int[] rates = {10, 5, 12, 8, 15, 3, 7};
int k = 3;
int[] maxes = maxSlidingWindow(rates, k);
System.out.print("Window maximums: ");
for (int m : maxes) System.out.print(m + " ");
}
}
Window maximums: 12 12 15 15 15
Why store indices instead of values?
Evicting the front of the deque depends on knowing whether an element has slid out of the window. You can only determine that by comparing the index with the current window boundary (i - k). If you stored values instead of indices, you would not know when to evict the front.
// Front eviction uses the INDEX:
if (deque.peekFirst() <= i - k) deque.pollFirst();
// If we stored values instead:
// deque.peekFirst() returns a value like 10
// We cannot compare 10 <= i - k (meaningless)
How does the decreasing invariant work?
Before adding a new index, you pop from the back every index whose value is less than or equal to the new value. These elements can never be the maximum of any future window because the new element is both larger and more recent. After this cleanup, the deque's values are strictly decreasing from front to back.
// Walkthrough: nums = [10, 5, 12, 8, 15], k=3
// i=0: deque=[], push 0 -> deque=[0] (values: [10])
// i=1: nums[0]=10 > 5, push 1 -> deque=[0,1] (values: [10,5])
// i=2: nums[1]=5 <= 12, pop 1; nums[0]=10 <= 12, pop 0
// push 2 -> deque=[2] (values: [12])
// i >= k-1, result[0] = nums[2] = 12
// i=3: nums[2]=12 > 8, push 3 -> deque=[2,3] (values: [12,8])
// front=2, 2 <= 3-3=0? No. result[1] = nums[2] = 12
// i=4: nums[3]=8 <= 15, pop 3; nums[2]=12 <= 15, pop 2
// push 4 -> deque=[4] (values: [15])
// result[2] = nums[4] = 15
How is this different from a naive approach?
The naive approach scans each window for its maximum, giving O(n*K) time. A heap-based approach gives O(n log K) because removing expired elements costs log time. The monotonic deque achieves O(n) because each index enters and leaves at most once.
| Approach | Time | Space | Key Property |
|---|---|---|---|
| Naive scan | O(n*K) | O(1) | Recomputes each window |
| Max-heap | O(n log K) | O(K) | Lazy removal from heap |
| Monotonic deque | O(n) | O(K) | Each index enters/leaves once |
// Naive O(n*K):
for (int i = 0; i <= n - k; i++) {
int max = Integer.MIN_VALUE;
for (int j = i; j < i + k; j++) max = Math.max(max, nums[j]);
result[i] = max;
}
What about using <= vs < for back eviction?
Using <= (less than or equal) on the back eviction means equal values are also popped. This is correct because if two elements have the same value, the newer one is strictly better: it stays in the window longer. Using strict < would leave stale equal-valued indices that serve no purpose.
// Correct: use <= to pop equal values too
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
// Equal values from earlier are now useless because the newer one
// has the same value but stays in the window longer
What are the edge cases?
A window of size 1 returns the array itself. A window equal to the array length returns a single-element result (the global maximum). An empty array returns an empty result.
package com.bank.service;
public class SlidingWindowMaxEdge {
public static void main(String[] args) {
// k = 1: each element is its own maximum
int[] r1 = SlidingWindowMaximum.maxSlidingWindow(new int[]{3, 1, 4}, 1);
for (int v : r1) System.out.print(v + " "); // 3 1 4
System.out.println();
// k = array length: single result = global max
int[] r2 = SlidingWindowMaximum.maxSlidingWindow(new int[]{3, 1, 4}, 3);
for (int v : r2) System.out.print(v + " "); // 4
System.out.println();
}
}
3 1 4
4
What are common mistakes?
The most common mistake is forgetting the front eviction check, which leaves expired indices in the deque and reports a maximum from outside the current window.
// WRONG: no front eviction
deque.offerLast(i);
// Missing: if (deque.peekFirst() <= i - k) deque.pollFirst();
// This can report a maximum that is no longer in the window
// CORRECT: always check front eviction
deque.offerLast(i);
if (deque.peekFirst() <= i - k) deque.pollFirst();
When should you use a monotonic deque?
Use a monotonic deque whenever you need the maximum (or minimum) of a sliding window in linear time. In banking, this applies to tracking rolling peak transaction rates, peak balances, or peak load over a sliding time window.
package com.bank.service;
public class PeakRateMonitor {
public static void main(String[] args) {
int[] perSecondRates = {45, 60, 33, 72, 55, 88, 41, 67};
int windowSize = 4;
int[] peaks = SlidingWindowMaximum.maxSlidingWindow(perSecondRates, windowSize);
System.out.print("Rolling peak rates: ");
for (int p : peaks) System.out.print(p + " ");
}
}
Rolling peak rates: 72 72 88 88 88
What should a senior engineer know?
A senior engineer should explain the amortized O(n) analysis: each of the n indices is pushed once and popped at most once, giving at most 2n deque operations total. The deque never holds more than K indices, bounding the space. The decreasing invariant guarantees the front is always the maximum, and the back-eviction with <= (not <) prevents stale equal-valued duplicates.
What are common interview follow-up questions?
- Interviewers commonly ask:
- Why store indices, not values? (Front eviction depends on position.)
- Why <= not
- Time complexity? (O(n) amortized, each index pushed and popped at most once.)
- Can you compute sliding window minimum? (Same deque, but keep increasing order and pop back when value >= new.)
Visual Overview
Monotonic deque on [10, 5, 12, 8, 15, 3, 7], k=3
i=0: deque=[0] values=[10]
i=1: deque=[0,1] values=[10,5]
i=2: pop 1,0; push 2 deque=[2] values=[12]
result[0] = 12
i=3: push 3 deque=[2,3] values=[12,8]
result[1] = 12
i=4: pop 3,2; push 4 deque=[4] values=[15]
result[2] = 15
i=5: push 5 deque=[4,5] values=[15,3]
result[3] = 15
i=6: pop 5; push 6 deque=[4,6] values=[15,7]
evict front? 4 <= 6-3=3? No
result[4] = 15
Result: [12, 12, 15, 15, 15]
Deque invariant (decreasing values):
front ─── biggest ──── newest ─── back
┌───┬───┬───┐
│15 │ 7 │ │ values always decrease
└───┴───┴───┘
Key Takeaway
Sliding Window Maximum returns the maximum of every window of size K using a monotonic deque of indices kept in decreasing order of their values. For each new element, you pop from the back every index whose value is less than or equal to the new value, because those can never be the maximum while the newer, larger value is in the window. Then you push the new index, evict the front if it has slid out, and read the front as the window maximum.
Storing indices rather than values is essential because evicting the front depends on position. You need to compare the front index with the current window boundary to know when an element has aged out. The decreasing invariant guarantees the front is always the maximum: any smaller earlier value was already popped when a larger value arrived.
The headline property is O(n) total time. Each of the n indices is pushed once and popped at most once, giving at most 2n deque operations across the entire array. The deque never holds more than K indices, bounding space to O(K).
In the operations dashboard at the National Bank of India, Rajesh tracks the rolling peak transaction rate over every K-minute window to spot load spikes. The rate series streams continuously and is long, so recomputing each window's maximum from scratch would be too slow. The monotonic deque gives each window's maximum in amortized constant time per element, so the alert fires the instant the rate falls a set distance below the rolling peak.
Remember one sentence: maintain a decreasing deque of indices, pop smaller values from the back, evict expired indices from the front, and the front is always the window maximum.
---