Sliding Window: Reuse Your Work

A fixed window

Question: which 3 days in a row had the most sales? Adding 3 numbers for every start position repeats work. Instead, slide a window: add the day coming in, subtract the day going out.

public class Main {
    public static void main(String[] args) {
        int[] sales = {5, 2, 8, 1, 9, 4, 3};
        int k = 3;
        int window = 0;
        for (int i = 0; i < k; i++) window += sales[i];
        int best = window, bestStart = 0;
        for (int end = k; end < sales.length; end++) {
            window += sales[end] - sales[end - k];      // one in, one out
            if (window > best) {
                best = window;
                bestStart = end - k + 1;
            }
        }
        System.out.println("best " + k + " days start at day " + bestStart + " with " + best);
    }
}

Output

best 3 days start at day 2 with 18

A window that grows and shrinks

Question: what is the longest stretch with at most 2 rainy days (1 = rain)? Move right one step at a time. When the window breaks the rule, move left until it's fine again:

public class Main {
    public static void main(String[] args) {
        int[] rain = {0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0};
        int allowed = 2;
        int left = 0, rainy = 0, best = 0;
        for (int right = 0; right < rain.length; right++) {
            rainy += rain[right];
            while (rainy > allowed) {        // too many rainy days: shrink
                rainy -= rain[left];
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        System.out.println("longest stretch: " + best + " days");
    }
}

Output

longest stretch: 7 days

left and right each only move forward, so even with the inner while the total work is O(n).

Tip: Spot the pattern: the question says “in a row”, “contiguous”, “substring” or “subarray”? Think sliding window or prefix sums.