Two Pointers and the Window

Most array interview questions are not about arrays. They are about avoiding looking at every pair. The nested loop that tries everything is O(n²); the pass that eliminates a row or column of possibilities per step is O(n). Two patterns do that eliminating — walking a sorted array from both ends, and sliding a window across it — and a third, the prefix sum, extends the window idea to questions about totals.

The pair matrix you never build

Every pair in an array is a cell in an n×n matrix. A nested loop visits all of them. Two pointers on a sorted array visit one per step, along the edges.

function pairWithSum(sorted: number[], target: number): [number, number] | null {
  let left = 0
  let right = sorted.length - 1

  while (left < right) {
    const sum = sorted[left] + sorted[right]
    if (sum === target) return [left, right]
    if (sum < target) left += 1
    else right -= 1
  }
  return null
}

Why each step is safe to take: if the sum is too small, sorted[left] plus every remaining candidate to its left of right is also too small — sorted[right] is the largest partner left, so left is done and can advance. The too-large case is symmetric. That argument is the entire algorithm, and it only holds because the array is sorted: the ordering is what lets one comparison discard a whole row or column of the pair matrix. On an unsorted array the pattern is a bug, not a shortcut.

function pairWithSum(sorted: number[], target: number): [number, number] | null {
  let left = 0
  let right = sorted. - 1

  while (left < right) {
    const sum = sorted[left] + sorted[right]
    if (sum === target) return [left, right]
    if (sum < target) left += 1
    else right -= 1
  }
  return null
}

The window is an invariant, not a pair of indices

A sliding window is one idea wearing several costumes: longest stretch without a repeat, shortest stretch that sums past a threshold. The idea is an invariant — a sentence that is true about start..end at every step — and the algorithm is "grow the right edge, repair the invariant by moving the left edge, then measure".

For the longest stretch without a repeated character, the invariant is no character appears twice between start and i. The repair move is the one everyone gets wrong:

export function longestUniqueSpan(input: string): number {
  const lastSeen = new Map<string, number>()
  let start = 0
  let best = 0

  for (let i = 0; i < input.length; i++) {
    const ch = input[i] as string
    const previous = lastSeen.get(ch)
    if (previous !== undefined && previous >= start) {
      start = previous + 1
    }
    best = Math.max(best, i - start + 1)
    lastSeen.set(ch, i)
  }
  return best
}

Two details carry the whole thing. previous >= start — the map remembers positions from before the window, and a repeat outside the window is not a repeat; honoring a stale position moves start backwards and invents characters the window already excluded. And start only ever moves forward, which is what makes the whole pass linear: both edges travel the string at most once, even though the loop looks like it could oscillate.

const previous = lastSeen.(ch)
if (previous !== undefined && previous >= start) {
  start = previous + 1
}

Prefix sums: the window's cousin

A prefix sum table answers "how much is between here and there" for any here and there, after one pass of preparation. The trick is one sentinel: the sum of no elements is 0, and it sits at index 0.

export class PrefixSums {
  readonly #prefix: number[]

  constructor(nums: number[]) {
    this.#prefix = [0]
    let running = 0
    for (const value of nums) {
      running += value
      this.#prefix.push(running)
    }
  }

  rangeSum(left: number, inclusiveRight: number): number {
    return (this.#prefix[inclusiveRight + 1] as number) - (this.#prefix[left] as number)
  }
}

Without the sentinel, rangeSum needs a branch for left === 0; with it, every range is the same one-line subtraction. Off-by-one errors in prefix sums are almost always a missing sentinel, not a bad formula. The pattern shows up disguised everywhere: range queries, running balances, "how many events happened between two timestamps", and — with the values squared first — variance over a window.

How to debug all three

These patterns fail by drifting, not by crashing, so print the state that defines them. For two pointers, print left, right and the sum every iteration — a pointer that moves the wrong way is visible instantly. For a window, print [start, i] and the invariant's value; the iteration where the invariant breaks points at the repair move you skipped. For prefix sums, print the table — it should start with 0, end with the total, and be non-decreasing for non-negative inputs. In the exercises for this concept, a wrong two-pointer answer is nearly always the comparison (< where the window is still valid) and a wrong window answer is nearly always a left edge that moved backwards.

Where this bites

• Two pointers on an unsorted array. The elimination argument depends on order; sort first (and remember indices change), or the pattern silently returns wrong pairs that look plausible. Counter: ask "what does one comparison rule out?" — if the answer is nothing, the pattern does not apply.
• A window that shrinks after measuring. Measuring before the repair move reports stretches that violate the invariant. Counter: the order is always repair, then measure — write the invariant as a comment above the loop and keep the two lines adjacent.
• start = previous + 1 without the >= start guard. The map's memory is older than the window; obeying it moves start backwards and re-admits an excluded character. Counter: treat every remembered position as stale until compared against the window's own edges.
• Prefix sums with no sentinel. The left === 0 branch looks harmless until someone forgets it in one of twelve call sites. Counter: the empty sum is a real row of the table — allocate it once and let every query share the same subtraction.