templates · Two pointers, windows & prefix sums

Sliding window (variable size)

  • "Longest" or "shortest" contiguous subarray or substring
  • A rule about what is inside the window: no repeats, at most k zeros, sum at least target
  • The rule moves one way: growing the window only pushes it further (more repeats, a bigger sum), and shrinking only pulls it back

Sliding window (variable size)

the one rule

The invariant

After the inner while loop, s[left..right] is the longest valid window that ends at right.

write it from memory

The template

longest valid window

javajava.util.*
/** Longest window that is still valid. Example: longest substring with no repeated character. */static int longestValid(String s) {    int[] count = new int[128];                       // what is inside the window    int best = 0;    int left = 0;    for (int right = 0; right < s.length(); right++) {        char in = s.charAt(right);        count[in]++;                                  // grow: take s[right] in        while (count[in] > 1) {                       // window broken?            count[s.charAt(left)]--;                  // shrink: drop s[left]            left++;        }        best = Math.max(best, right - left + 1);      // window is valid here    }    return best;}

Shrink while the window is broken, then record. The answer is taken after the loop, when the window is valid again.

fill in the blanks — only these lines change per problem

  1. line 3What you track about the window: a count array, a HashMap, a sum, or a number of zeros.
  2. line 8How the new element right changes that state.
  3. line 9The rule that makes the window invalid, e.g. zeros > k or count[in] > 1.
  4. line 10How dropping left undoes the add. It must be the exact mirror of the add line.

shortest window that reaches a goal

javajava.util.*
/** Shortest window that reaches a goal. Example: shortest subarray with sum >= target (all numbers positive). */static int shortestReaching(int[] nums, int target) {    long sum = 0;                                     // what is inside the window    int best = Integer.MAX_VALUE;    int left = 0;    for (int right = 0; right < nums.length; right++) {        sum += nums[right];                           // grow: take nums[right] in        while (sum >= target) {                       // goal reached?            best = Math.min(best, right - left + 1);  // record, then try smaller            sum -= nums[left];                        // shrink: drop nums[left]            left++;        }    }    return best == Integer.MAX_VALUE ? 0 : best;      // 0 = no window works}

Here you record inside the loop: every time the goal is met, note the size, then shrink to try a smaller one.

fill in the blanks — only these lines change per problem

  1. line 8The goal condition, e.g. sum >= target or "every needed letter is covered".
  2. line 14What to return when no window ever works: 0, -1 or an empty string, as the problem says.

complexity

What it costs

time O(n)
right moves n times and left moves at most n times in total, so the two loops together do at most 2n steps.
space O(1)
Only the window's state: a count array of fixed size (128 slots, one per ASCII character) or a running sum. With a HashMap over an open alphabet it is O(number of distinct characters).

watch out

Common bugs

  • Using if instead of while to shrink. One step may not be enough to fix the window.
  • Recording the answer in the wrong place: after the loop for "longest", inside it for "shortest".
  • Using it with negative numbers. Then shrinking can make the sum bigger, the rule above breaks, and you need prefix sums instead.

use it

Practise it on

learn it properly