templates · Two pointers, windows & prefix sums

Two pointers (opposite ends)

  • The array is sorted (or you can sort it) and you need a pair with some sum
  • A score that depends on both ends, like width × the shorter height
  • Reverse or compare from both ends: palindromes, reversing in place

Two pointers (opposite ends)

the one rule

The invariant

Every pair outside [left, right] is already checked or proven useless, so the answer can only be inside.

write it from memory

The template

find a pair in a sorted array

javajava.util.*
/** Find two positions whose values add up to target, in a SORTED array. Returns {i, j} or {-1, -1}. */static int[] pairWithSum(int[] sorted, int target) {    int left = 0, right = sorted.length - 1;          // one pointer at each end    while (left < right) {                            // they meet → every pair checked        long sum = (long) sorted[left] + sorted[right];        if (sum == target) return new int[] {left, right};        if (sum < target) left++;                     // need bigger → move left up        else right--;                                 // need smaller → move right down    }    return new int[] {-1, -1};}

Sum too small? Only moving left up can make it bigger. Too big? Only moving right down helps. That is the whole proof.

fill in the blanks — only these lines change per problem

  1. line 5How the two ends combine: a sum, a difference, or a three-sum's nums[i] + .... Use long if it can overflow.
  2. line 6What to do on a hit: return, or record it and move both pointers (skip duplicates for 3Sum).
  3. line 7When to move left: the combined value is too small.

best pair over the whole array

javajava.util.*
/** Best pair over the whole array. Example: container with most water. */static long bestPair(int[] height) {    int left = 0, right = height.length - 1;    long best = 0;    while (left < right) {        long area = (long) Math.min(height[left], height[right]) * (right - left);        best = Math.max(best, area);        if (height[left] < height[right]) left++;     // the shorter side can never do better        else right--;    }    return best;}

Score the current pair, then drop the side that cannot be part of a better answer.

fill in the blanks — only these lines change per problem

  1. line 6The score of the current pair, e.g. min(h[l], h[r]) * (r - l).
  2. line 8Which side to drop. Always the one that can never give a better score.

complexity

What it costs

time O(n)
Each step moves left up or right down by one, and they meet after at most n − 1 steps.
space O(1)
Two index variables. If you sort first, add O(n log n) time.

watch out

Common bugs

  • Using it on an unsorted array for a pair sum. The "too small → move left" rule only works when the array is sorted.
  • Writing while (left <= right) for pairs. Then left == right uses the same element twice.
  • In 3Sum, forgetting to skip equal values after a hit, so the same triplet is reported again.

use it

Practise it on

learn it properly