Lesson 7.3 · Sliding Window

Variable Windows: Finding the Shortest

For "shortest window that satisfies X", grow until it's satisfied, then shrink while it stays satisfied, recording the size at each shrink.

12 min

Think of it like this

Looking for the shortest stretch of a shopping street that has a bakery, a pharmacy and an ATM. Walk forward until you've passed all three, then step your start forward as long as all three are still inside, noting how short the stretch got.

1.The mirror image of "longest"

For longest windows you shrink while invalid and measure after. For shortest windows you shrink while valid and measure inside the shrinking loop, because every valid window is a candidate and shrinking makes it shorter.

ShortestWindow.java

public class Main {
    // shortest subarray with sum >= target (all values positive)
    static int minLen(int[] a, int target) {
        int left = 0, sum = 0, best = Integer.MAX_VALUE;
        for (int right = 0; right < a.length; right++) {
            sum += a[right];
            while (sum >= target) {                 // valid: record, then try shorter
                best = Math.min(best, right - left + 1);
                sum -= a[left++];
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
    public static void main(String[] args) {
        System.out.println(minLen(new int[]{2, 3, 1, 2, 4, 3}, 7));
    }
}

Output

2.When windows don't work

Shrinking only helps if removing an element moves the summary in a predictable direction. With all-positive numbers, removing an element always lowers the sum. With negative numbers that's false, and windows give wrong answers: use prefix sums with a hash map instead (Prefix Sum module).

Quick check

Why does "shortest subarray with sum ≥ k" break with a sliding window when negatives are allowed?

Remember

Shortest: shrink while valid, record inside the loop.
Windows need a monotonic summary (e.g. positive numbers for sums).

Common mistakes

Recording after the shrink loop for shortest problems (the window is invalid by then).
Using windows with negative numbers.

Command Palette

Variable Windows: Finding the Shortest

1.The mirror image of "longest"

2.When windows don't work