Sliding window: pay once per shift

Maintain, do not recompute

A sliding window is a disciplined way of saying: instead of recomputing a property of every length-k substring from scratch, I will slide a window of size k across the array and update the property in O(1) per shift by seeing who left the window and who entered. This turns a naïve O(n·k) algorithm into a tight O(n) one.

Fixed-size window: maximum sum of k consecutive elements

public static int maxSumK(int[] a, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i];
    int best = sum;
    for (int i = k; i < a.length; i++) {
        sum += a[i] - a[i - k];  // add entering, subtract leaving
        best = Math.max(best, sum);
    }
    return best;
}

Variable-size window: shortest subarray with sum ≥ target

When the window can grow and shrink, we use two indices (left, right). Expand right until the property is satisfied, then contract left while it still holds, recording the best answer. Each index moves forward at most n times, so the total work is O(n).

Open interactive lab →