Sliding window

Written Explanation

Subarrays and windows

A subarray is a block of consecutive items of an array. For {2, 1, 5, 1, 3, 2}, the block {1, 5, 1} (indexes 1 to 3) is a subarray, but {2, 5} is not, because it skips an item. For text, the same idea is called a substring.

A window is how we describe a subarray while we scan: two indexes, left and right, where the window contains every item from a[left] to a[right], both ends included.

Length of the window: right - left + 1. When left == right the window holds exactly one item, and right - left would wrongly say 0. This formula is the most common source of off-by-one bugs in this topic; the demo lesson shows one on purpose.

The sliding window differs from the two pointers of the last lesson in one way: here both indexes only move forward (to the right). right adds an item to the window. left removes one.

Fixed-size window

Problem: find the largest sum of k consecutive items.

Slow idea: for each start position, add k items. That is about n × k additions, O(n × k).

Window idea: keep a running sum of the current window. As the window slides one step, add the new item and subtract the item that just fell out of the frame.

static int bestSum(int[] a, int k) {
    int sum = 0, best = Integer.MIN_VALUE;
    for (int i = 0; i < a.length; i++) {
        sum += a[i];                       // item enters on the right
        if (i >= k) sum -= a[i - k];       // item leaves on the left
        if (i >= k - 1) best = Math.max(best, sum);   // window is full
    }
    return best;
}

Reading it line by line, with i as the right edge:

• For the first k - 1 items the window is not full yet, so we only add.
• From i = k onward, the item at i - k has just left the window, so we subtract it. The window now is [i - k + 1, i], which has exactly k items.
• From i = k - 1 onward the window is full, so its sum is a valid candidate for best.

best starts at Integer.MIN_VALUE, not 0, because with all-negative data the true maximum is below zero.

Why it is O(n)

Each item is added once (when it enters) and subtracted at most once (when it leaves). That is at most about 2n operations, regardless of k. The "slow idea" re-adds the same items again and again; the window never does. Extra space is O(1): a few variables.

Variable-size window

Often the window size is not given. Instead there is a rule, and you want the longest or shortest window that satisfies it. The pattern:

1. Move right forward, adding a[right] to the window.
2. While the rule is broken, move left forward, removing items, until the rule holds again.
3. Now the window is valid; update the answer.

Problem: the longest subarray whose sum is at most limit, for non-negative numbers.

static int longestAtMost(int[] a, int limit) {
    int left = 0, sum = 0, best = 0;
    for (int right = 0; right < a.length; right++) {
        sum += a[right];                              // grow
        while (sum > limit) { sum -= a[left]; left++; }   // shrink until valid
        best = Math.max(best, right - left + 1);
    }
    return best;
}

It looks like a nested loop, but it is still O(n). right moves forward n times in total and left also moves forward at most n times in total, because neither ever goes back. The inner while does not restart; it continues from where left was. In total there are at most 2n pointer moves.

When does shrinking work? The while loop relies on a property: removing an item from the left makes the sum smaller, so shrinking eventually fixes the rule. That is true for non-negative numbers. With negative numbers the sum could go up when an item leaves, and this simple window does not work. This is why a good first question is "is the data non-negative?".

Is it a window problem?

Look for these signs:

• The question is about a contiguous block (subarray or substring), not an arbitrary choice of items.
• The answer is a maximum, minimum, longest, shortest, or count over such blocks.
• Adding an item or removing an item changes a running value (a sum, a count, a set) in O(1).

If the items need not be consecutive, a window is the wrong tool.