Lesson 7.1 · Sliding Window

Fixed-Size Windows

Slide a window of exactly k elements: add the element entering on the right, remove the one leaving on the left.

12 min

Think of it like this

A train window that always shows exactly three houses. As the train moves, one house appears on the right and one disappears on the left. To know the total number of lights in view, you don't recount all three: you add the new house's lights and subtract the old one's.

1.From O(n·k) to O(n)

The slow way computes each window's sum with a loop of k steps: O(n·k). Neighbouring windows share k − 1 elements, so recomputing is wasted work.

Instead keep sum. When right enters, add a[right]; once the window is longer than k, subtract a[right − k], the element that just left. When the window is full (right ≥ k − 1), it's a complete window to evaluate.

▶ Dry run: Sums of every window of 3a = [2, 1, 5, 1, 3, 2], k = 3

State(vars)

sum = 8best = 8

Step 1/4First full window [2, 1, 5]: sum 8.

2.The code

The same loop works for averages, counts of vowels in each window, or letter counts in each window (for anagram problems).

FixedWindow.java

public class Main {
    static int maxWindowSum(int[] a, int k) {
        int sum = 0, best = Integer.MIN_VALUE;
        for (int right = 0; right < a.length; right++) {
            sum += a[right];
            if (right >= k) sum -= a[right - k];
            if (right >= k - 1) best = Math.max(best, sum);
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(maxWindowSum(new int[]{2, 1, 5, 1, 3, 2}, 3));
    }
}

Output

Remember

Add the entering element, subtract the leaving one (a[right − k]).
Evaluate only full windows (right ≥ k − 1).
O(n) regardless of k.

Common mistakes

Evaluating partial windows at the start.
Subtracting a[right − k + 1] (off by one).

Command Palette

Fixed-Size Windows

1.From O(n·k) to O(n)

2.The code