templates · Two pointers, windows & prefix sums

Sliding window (fixed size)

  • "Every subarray (or substring) of length k"
  • Find an anagram or permutation of p inside s: the window size is p.length()
  • Best sum, average or count over windows of one given size

Sliding window (fixed size)

the one rule

The invariant

Before each check, the window is exactly [right - k + 1, right]: k elements, and the state matches them.

write it from memory

The template

best sum of k in a row

javajava.util.*
/** Best sum of any k consecutive numbers (1 <= k <= n). Example: maximum average subarray = best / k. */static long bestWindowSum(int[] nums, int k) {    long sum = 0;                                     // state of the current window    for (int i = 0; i < k; i++) sum += nums[i];       // build the first window    long best = sum;    for (int right = k; right < nums.length; right++) {        sum += nums[right];                           // one element comes in        sum -= nums[right - k];                       // the one k places back goes out        best = Math.max(best, sum);                   // every window has size k here    }    return best;}

Build the first window, then slide: one in, one out. Never re-add the whole window.

fill in the blanks — only these lines change per problem

  1. line 3What describes the window: a sum, a count array, a number of vowels.
  2. line 7How nums[right] coming in changes the state.
  3. line 8How nums[right - k] going out changes the state. The exact mirror of the add.
  4. line 9What you check for each window: best so far, or "does it match?"

window of letter counts

javajava.util.*
/** Every start index where the window of size p.length() is an anagram of p (lowercase letters). */static List<Integer> anagramStarts(String s, String p) {    List<Integer> starts = new ArrayList<>();    int k = p.length();    if (k > s.length()) return starts;    int[] need = new int[26], have = new int[26];    for (int i = 0; i < k; i++) {        need[p.charAt(i) - 'a']++;        have[s.charAt(i) - 'a']++;    }    if (Arrays.equals(need, have)) starts.add(0);    for (int right = k; right < s.length(); right++) {        have[s.charAt(right) - 'a']++;                // in        have[s.charAt(right - k) - 'a']--;            // out        if (Arrays.equals(need, have)) starts.add(right - k + 1); // window is s[right-k+1..right]    }    return starts;}

Same slide, but the state is a count array. Bas itna yaad rakho: in at right, out at right - k.

fill in the blanks — only these lines change per problem

  1. line 15The window's start index is right - k + 1. Record that, not right.

complexity

What it costs

time O(n)
Each step adds one element and removes one: O(1) work per step. The anagram version compares two 26-sized arrays, still O(26 · n) = O(n).
space O(1)
A running sum, or a count array of fixed size (26 letters).

watch out

Common bugs

  • Forgetting the very first window: checking only inside the slide loop misses the window that starts at 0.
  • Removing nums[right - k + 1] instead of nums[right - k]. Off by one: you drop an element that is still inside the window, so the state no longer matches any real window.
  • Using int for the sum when k values near 10⁹ can add up past 2³¹ − 1. Use long.

use it

Practise it on

learn it properly