A fixed-size window
Picture a train window and a long row of houses. As the train moves, one house appears on the right and one disappears on the left. You don’t need to look at every house in the window again; you only update what changed.
A window is a range of the array between two indices, left and right:
- Fixed size: the window always holds k elements. Each step, one element enters on the right and one leaves on the left.
- Variable size: the window grows on the right while it’s valid, and shrinks from the left when it breaks a rule (too big a sum, a repeated character). You’re looking for the longest or shortest valid window.
A sliding window maintains an aggregate over a contiguous range [left, right] incrementally, so each element is added once and removed at most once: O(n) total, provided the aggregate supports O(1) (or O(log k)) insert and delete. Sums, counts and frequency maps do; maximums need a monotonic deque.
The variable-size version is only correct when the validity condition is monotonic: if a window is invalid, every larger window containing it is invalid too (and vice versa for “at least” conditions). That’s why it works for non-negative sums and character counts, and silently fails with negative numbers. The Detailed version covers that, the “exactly K = at most K − at most K−1” trick, and the deque for window maximums.
func maxSum(_ nums: [Int], _ k: Int) -> Int {
var sum = nums[0..<k].reduce(0, +) // the first window
var best = sum
for right in k..<nums.count {
sum += nums[right] - nums[right - k] // one element in, one element out
best = max(best, sum)
}
return best
}fun maxSum(nums: IntArray, k: Int): Int {
var sum = (0 until k).sumOf { nums[it] } // the first window
var best = sum
for (right in k until nums.size) {
sum += nums[right] - nums[right - k] // one element in, one element out
best = maxOf(best, sum)
}
return best
}static int maxSum(int[] nums, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += nums[i]; // the first window
int best = sum;
for (int right = k; right < nums.length; right++) {
sum += nums[right] - nums[right - k]; // one element in, one element out
best = Math.max(best, sum);
}
return best;
}function maxSum(nums: number[], k: number): number {
let sum = 0;
for (let i = 0; i < k; i++) sum += nums[i]; // the first window
let best = sum;
for (let right = k; right < nums.length; right++) {
sum += nums[right] - nums[right - k]; // one element in, one element out
best = Math.max(best, sum);
}
return best;
}The trick is in one line: sum += nums[right] - nums[right - k]. When the window moves one step right, the new element nums[right] comes in and the element k places back, nums[right - k], falls out. Each step costs the same, whether k is 3 or 3,000.
A window that loses the wrong element
Off-by-one errors love sliding windows. Here’s a version that adds and removes inside one loop. Which line is wrong?
Tap the line with the bug.
func maxSum(_ nums: [Int], _ k: Int) -> Int {
var sum = 0
var best = Int.min
for i in nums.indices {
sum += nums[i]
if i >= k { sum -= nums[i - k + 1] }
if i >= k - 1 { best = max(best, sum) }
}
return best
}fun maxSum(nums: IntArray, k: Int): Int {
var sum = 0
var best = Int.MIN_VALUE
for (i in nums.indices) {
sum += nums[i]
if (i >= k) sum -= nums[i - k + 1]
if (i >= k - 1) best = maxOf(best, sum)
}
return best
}static int maxSum(int[] nums, int k) {
int sum = 0;
int best = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (i >= k) sum -= nums[i - k + 1];
if (i >= k - 1) best = Math.max(best, sum);
}
return best;
}function maxSum(nums: number[], k: number): number {
let sum = 0;
let best = -Infinity;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
if (i >= k) sum -= nums[i - k + 1];
if (i >= k - 1) best = Math.max(best, sum);
}
return best;
}Hint: With k = 3 and i = 3, the window should be indices 1, 2 and 3. Which index has to leave?
When i = 3 and k = 3, the window moves from indices 0–2 to 1–3, so index 0 must leave: that’s i - k. The code removes nums[i - k + 1], index 1, which is still inside the window, and keeps index 0 forever. Every sum after the first window is wrong, and tests with equal numbers (like [1, 1, 1, 1]) don’t catch it.
if i >= k { sum -= nums[i - k] }if (i >= k) sum -= nums[i - k]if (i >= k) sum -= nums[i - k];if (i >= k) sum -= nums[i - k];A quick check for any window code: write down the indices of one window by hand (here, right - k + 1 ... right), and the element that leaves is the one just before the first.
Predict the output
What gets printed?
print(maxSum([2, 1, 5, 1, 3, 2], 3))println(maxSum(intArrayOf(2, 1, 5, 1, 3, 2), 3))System.out.println(maxSum(new int[] {2, 1, 5, 1, 3, 2}, 3));console.log(maxSum([2, 1, 5, 1, 3, 2], 3));The windows of 3 are [2, 1, 5] = 8, [1, 5, 1] = 7, [5, 1, 3] = 9 and [1, 3, 2] = 6. The highest is 9. Notice the second sum: 8 + 1 − 2 = 7. Adding the new element and subtracting the one that left gives each sum without re-adding the whole window.
Window aggregates that aren’t sums
| Aggregate | Structure | Cost per step |
|---|---|---|
| sum, count | a number | O(1) |
| distinct values, anagram check | a frequency map (or an IntArray(26)) plus a “matches” counter | O(1) |
| max or min | a monotonic deque of indices | O(1) amortized |
| median, k-th largest | two heaps with lazy deletion, or an order-statistic tree | O(log k) |
The frequency map with a “how many characters currently match” counter is what makes Minimum Window Substring O(n): instead of comparing two maps every step (O(alphabet)), update the counter when a single character’s count crosses its required value.
Sliding Window Maximum
Given an array nums and a window size k, return the maximum of each window as it slides from left to right.
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
windows: [1 3 -1] [3 -1 -3] [-1 -3 5] [-3 5 3] [5 3 6] [3 6 7]
output: [3, 3, 5, 5, 6, 7]The naive answer is O(n·k), and a heap gives O(n log n). Find an O(n) solution.
›
When a new element arrives, every element in the window that’s smaller than it can never be a window maximum again: the new one is bigger and will stay in the window longer.
›
Keep a deque of indices whose values decrease from front to back. Before adding index i, pop smaller-or-equal values from the back; drop the front if it has left the window. The front is always the current maximum.
SolutionTry it yourself firstTime O(n)Space O(k)
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
var result: [Int] = []
var deque: [Int] = [] // indices; values decrease front to back
var head = 0 // the front, so removing from the front is O(1)
for i in nums.indices {
if head < deque.count && deque[head] <= i - k { head += 1 }
while deque.count > head && nums[deque[deque.count - 1]] <= nums[i] { deque.removeLast() }
deque.append(i)
if i >= k - 1 { result.append(nums[deque[head]]) }
}
return result
}fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
val result = IntArray(nums.size - k + 1)
val deque = ArrayDeque<Int>() // indices; values decrease front to back
for (i in nums.indices) {
if (deque.isNotEmpty() && deque.first() <= i - k) deque.removeFirst() // left the window
while (deque.isNotEmpty() && nums[deque.last()] <= nums[i]) deque.removeLast()
deque.addLast(i)
if (i >= k - 1) result[i - k + 1] = nums[deque.first()]
}
return result
}int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length - k + 1];
Deque<Integer> deque = new ArrayDeque<>(); // indices; values decrease front to back
for (int i = 0; i < nums.length; i++) {
if (!deque.isEmpty() && deque.peekFirst() <= i - k) deque.pollFirst();
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) deque.pollLast();
deque.addLast(i);
if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
}
return result;
}function maxSlidingWindow(nums: number[], k: number): number[] {
const result: number[] = [];
const deque: number[] = []; // indices; values decrease front to back
let head = 0; // the front, so we never call shift()
for (let i = 0; i < nums.length; i++) {
if (head < deque.length && deque[head] <= i - k) head++;
while (deque.length > head && nums[deque[deque.length - 1]] <= nums[i]) deque.pop();
deque.push(i);
if (i >= k - 1) result.push(nums[deque[head]]);
}
return result;
}Each index is pushed once and popped at most once, so the total is O(n) despite the inner while. Store indices, not values: you need them to know when the front has left the window, and they handle duplicates correctly. This monotonic deque is reusable: shortest subarray with sum at least K (with negatives), constrained subsequence sums, and jump-game DP with a window all use it. (The Swift and TypeScript versions never shrink their array, so for very long streams, compact it occasionally or use Deque from swift-collections.)
- The aggregate must support O(1) (or O(log k)) add and remove: sums and counts directly, frequency maps with a “matches” counter, a monotonic deque of indices for max/min, two heaps for medians.
- Check the leaving index by writing one window by hand: the window is
right - k + 1 ... right, soright - kleaves.
Check this part
In a fixed window of size k, which element leaves when right moves to a new index?
Which problems usually call for a sliding window?
What makes Sliding Window Maximum O(n)?
Why does the monotonic deque store indices rather than values?