Two Pointers and the Sliding Window

A huge fraction of array and string problems that look like they need nested loops actually don't. Two related patterns — two pointers and the sliding window — collapse that quadratic work into a single pass by never throwing away information you already computed. Once you recognize the shape, you'll see them everywhere. This post covers both, with templates you can reuse for each flavour.

The problem with the naive approach

Say you want the maximum sum of any 3 consecutive elements in an array. The obvious solution sums every window from scratch:

function maxSum(arr, k) {
  let best = -Infinity;
  for (let i = 0; i + k <= arr.length; i++) {
    let sum = 0;
    for (let j = i; j < i + k; j++) sum += arr[j]; // re-adds k elements
    best = Math.max(best, sum);
  }
  return best;
}

That inner loop re-adds k numbers for every position — O(n·k) work. But look at what happens when the window moves one step right: it loses its leftmost element and gains one on the right. Everything in the middle is identical. We're recomputing what we already knew.

The sliding window

Keep a running sum. When the window slides, subtract the element leaving and add the one entering — two operations, regardless of window size:

function maxSum(arr, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += arr[i]; // first window
  let best = sum;

  for (let end = k; end < arr.length; end++) {
    sum += arr[end] - arr[end - k]; // add new, drop old
    best = Math.max(best, sum);
  }
  return best;
}

One pass, O(n) time, O(1) space. The window carries its state forward instead of rebuilding it. For n = 100,000 and k = 1,000, that's the difference between about a hundred million additions and a couple of hundred thousand.

Fixed vs. dynamic windows

The example above is a fixed-size window. The more powerful variant is the dynamic window, where the right edge expands to include more and the left edge contracts when a constraint breaks. The classic is longest substring without repeating characters:

function longestUnique(s) {
  const seen = new Set();
  let left = 0, best = 0;

  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]); // shrink from the left until valid again
      left++;
    }
    seen.add(s[right]);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Each character is added once and removed at most once, so even with the inner while this is still O(n) — the pointers only ever move forward. This "amortised" argument — count total pointer moves, not loop nesting — is how to analyse every window solution.

The dynamic-window template

Most variable-window problems fit one template. Only three lines change from problem to problem — what to add, when the window is invalid, and what to remove:

function slidingWindow(items) {
  let left = 0, best = 0;
  const state = new Map();                 // whatever describes the window

  for (let right = 0; right < items.length; right++) {
    add(state, items[right]);              // 1. extend the window

    while (!isValid(state)) {              // 2. shrink until valid again
      remove(state, items[left]);          // 3. drop from the left
      left++;
    }

    best = Math.max(best, right - left + 1);   // record the answer
  }
  return best;
}

For "longest substring with at most k distinct characters", state is a count per character, isValid is state.size <= k, and remove decrements a count and deletes the key at zero. For "longest subarray with sum at most S" (non-negative numbers), state is a running sum. Once you can fill in those three blanks, you've solved the problem.

Shortest window: minimum window substring

"Longest valid window" grows and shrinks only when forced. "Shortest valid window" flips it: shrink as long as the window stays valid, recording the answer at each step. The classic is find the smallest substring of s that contains every character of t:

function minWindow(s, t) {
  const need = new Map();
  for (const ch of t) need.set(ch, (need.get(ch) ?? 0) + 1);
  let missing = t.length, left = 0, best = [0, Infinity];

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (need.has(ch)) {
      if (need.get(ch) > 0) missing--;
      need.set(ch, need.get(ch) - 1);      // may go negative: surplus
    }
    while (missing === 0) {                // valid: try to shrink
      if (right - left < best[1] - best[0]) best = [left, right];
      const out = s[left++];
      if (need.has(out)) {
        need.set(out, need.get(out) + 1);
        if (need.get(out) > 0) missing++;  // now short of this character
      }
    }
  }
  return best[1] === Infinity ? '' : s.slice(best[0], best[1] + 1);
}

minWindow('ADOBECODEBANC', 'ABC');   // 'BANC'

missing counts characters still needed, so checking validity is O(1) instead of comparing two maps. Negative counts in need represent surplus copies, which is what lets the left edge move past extra characters without breaking the window. Still O(n): each pointer only moves forward.

When the window doesn't work

Sliding windows rely on a property that's easy to miss: extending the window can only make the condition worse (or better) in one direction. With non-negative numbers, adding an element can only increase a sum, so "shrink until the sum is at most S" is valid. With negative numbers, a longer window might have a smaller sum, and shrinking from the left might not fix anything. "Subarray sum equals k" with negatives is a prefix sums problem with a hash map, not a window.

Two pointers

The sliding window is really a special case of the broader two pointers idea: maintain two indices and move them based on the data instead of brute-forcing every pair. The other common flavor is converging pointers on a sorted array — one from each end, walking toward the middle. Finding a pair that sums to a target:

function twoSumSorted(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    const sum = arr[lo] + arr[hi];
    if (sum === target) return [lo, hi];
    if (sum < target) lo++;  // need more → move the low end up
    else hi--;               // need less → move the high end down
  }
  return null;
}

Because the array is sorted, each comparison lets us rule out an entire row or column of the pair space — O(n) instead of the O(n²) of checking all pairs.

Why is moving the pointers safe — how do we know we didn't skip the answer? Suppose arr[lo] + arr[hi] is too small. Every pair using arr[lo] with any index below hi is even smaller (the array is sorted), so arr[lo] can't be part of any answer: discarding it loses nothing. The symmetric argument covers moving hi. Each step eliminates one element for good, which is why the loop runs at most n times.

Three numbers: 3Sum

Extending to triplets that sum to zero is the converging pattern inside a loop: fix one number, then run two pointers over the rest.

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const out = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;      // skip duplicate anchors
    let lo = i + 1, hi = nums.length - 1;
    while (lo < hi) {
      const sum = nums[i] + nums[lo] + nums[hi];
      if (sum < 0) lo++;
      else if (sum > 0) hi--;
      else {
        out.push([nums[i], nums[lo], nums[hi]]);
        while (lo < hi && nums[lo] === nums[lo + 1]) lo++;   // skip duplicates
        while (lo < hi && nums[hi] === nums[hi - 1]) hi--;
        lo++; hi--;
      }
    }
  }
  return out;
}

O(n²) — down from O(n³) for brute force — and the sort makes duplicate handling a matter of skipping equal neighbours.

Container with most water

Given heights of vertical lines, pick two that, with the x-axis, hold the most water. The area of a pair is width × min(height). Start with the widest pair and move inward — but which pointer?

function maxArea(h) {
  let lo = 0, hi = h.length - 1, best = 0;
  while (lo < hi) {
    best = Math.max(best, (hi - lo) * Math.min(h[lo], h[hi]));
    if (h[lo] < h[hi]) lo++; else hi--;    // move the shorter side
  }
  return best;
}

Dry run on [1, 8, 6, 2, 5, 4, 8, 3, 7]:

The reason to move the shorter side: the area is capped by the shorter line. Keeping it and moving the taller one inward can only shrink the width while the height stays capped — never better. So the shorter line has already been paired with its best possible partner, and can be discarded. That "this element can't be in any better answer" argument is the proof behind every converging two-pointer solution.

Read and write pointers

The third flavour moves two pointers in the same direction at different speeds: a read pointer scans every element, a write pointer marks where the next kept element goes. Removing duplicates from a sorted array in place:

function dedupeSorted(arr) {
  let write = 0;
  for (let read = 0; read < arr.length; read++) {
    if (read === 0 || arr[read] !== arr[read - 1]) arr[write++] = arr[read];
  }
  arr.length = write;
  return arr;
}

O(n) time and O(1) extra space — the same pattern partitions an array around a pivot in quick sort, and moves all zeros to the end. When the two pointers move at 1× and 2× speed through a linked list, it becomes the tortoise and hare cycle check.

How to spot them

Practice, in order

1. Maximum sum of a size-k subarray — fixed window.
2. Longest substring without repeating characters — dynamic window.
3. Longest substring with at most k distinct characters — dynamic window with counts.
4. Minimum window substring — shrink-while-valid.
5. Two sum on a sorted array, then 3Sum — converging pointers.
6. Container with most water — converging, moving the shorter side.
7. Remove duplicates in place, move zeros — read/write pointers.
8. Sliding window maximum — a window whose state needs a monotonic deque rather than a running total.

For each, say before coding which flavour it is and what the window's state is. That decision is the whole problem; the loop is a template.

Wrap-up

The common thread is don't recompute what hasn't changed. A sliding window updates its state incrementally as it moves; two converging pointers use sorted order to discard half the possibilities each step. Both trade a nested loop for a single forward sweep — the difference between code that scales and code that times out.

When you meet a new array or string problem, run through three questions in order: is it about a contiguous range (window)? Is the input sorted, or can I sort it without losing what's asked (converging pointers)? Am I rewriting the array in place (read/write)? One of the three fits a surprising share of the problems you'll see — and if none does, that's a strong hint to reach for a hash map, a heap or prefix sums instead.