Chapter 5 — Two Pointers

The brute force uses two loops. The insight uses two fingers.

Part 1: The Problem With Two Loops

Consider finding two numbers in a sorted array that sum to a target.

Brute force: try every pair.

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return [];
}

For n = 1000: up to 500,000 pair checks. O(n²).

The waste: we check pairs that can't possibly work. If nums[i] + nums[j] > target and the array is sorted, then nums[i] + nums[j+1] is even larger. We already know the answer is not to the right of j. Yet the inner loop keeps going.

Two Pointers is the technique that exploits this structure — eliminating large chunks of the search space with each comparison.

Part 2: What Two Pointers Actually Is

Two pointers means: maintain two indices into a data structure (usually an array or string), and move them according to a rule derived from the problem's structure.

Two things make this technique work:

1. The data has structure (sorted, or some monotonic property — as one pointer moves, some quantity only increases or only decreases).
2. Moving a pointer eliminates a region — you can prove that the answer cannot lie in the discarded region.

Without structure, moving a pointer eliminates nothing — you'd have to check everything, reverting to O(n²).

The two fundamental patterns:

Pattern A: Opposite Ends — one pointer starts at the left, one at the right. They move toward each other.
Use when: working with pairs (two elements, one from each end), palindrome checks, sorted arrays.

Pattern B: Same Direction (Fast / Slow) — both pointers start at left. One moves faster than the other.
Use when: finding a window, partitioning, removing duplicates in-place, cycle detection in linked lists.

Part 3: Pattern A — Opposite Ends

Two Sum II (Sorted Array)

Problem: Given a sorted array and a target, find two indices (1-indexed) whose values sum to target.

function twoSumSorted(numbers, target) {
  let left = 0;
  let right = numbers.length - 1;

  while (left < right) {
    const sum = numbers[left] + numbers[right];
    if (sum === target) return [left + 1, right + 1];
    if (sum < target) left++;   // sum too small, need bigger left value
    else right--;               // sum too big, need smaller right value
  }

  return [];  // no solution (problem guarantees one exists)
}

Why does moving left++ when sum is too small work?

Current pair: (numbers[left], numbers[right]). Sum is too small. We need to increase it.

• Can we increase it by moving right rightward? No — right is already at the boundary (right only moves leftward).
• Can we increase it by moving left leftward? No — left is already at the leftmost unused position.
• The only way to increase the sum: move left rightward to a larger value.

So we move left++. This eliminates every pair (left, x) for all x — not just (left, right), but the entire row of pairs with the current left. Because: for every possible right' where right' < right, numbers[left] + numbers[right'] < numbers[left] + numbers[right] < target. None of them work.

Similarly, right-- when sum is too large eliminates the entire column of pairs with the current right.

Dry run: twoSumSorted([2, 7, 11, 15], 9)

left=0, right=3. sum=2+15=17 > 9 → right=2.
left=0, right=2. sum=2+11=13 > 9 → right=1.
left=0, right=1. sum=2+7=9 === 9 → return [1, 2]. ✓

Complexity: O(n) time — left and right together take at most n steps total (each step moves one pointer, total moves ≤ n). O(1) space.

Part 4: Pattern A — Palindrome Check

Problem: Check if a string is a palindrome, ignoring non-alphanumeric characters and case.
isPalindrome("A man, a plan, a canal: Panama") → true

Two pointers from opposite ends, skip non-alphanumeric, compare.

function isPalindrome(s) {
  let left = 0, right = s.length - 1;

  while (left < right) {
    // Skip non-alphanumeric from left
    while (left < right && !isAlphanumeric(s[left])) left++;
    // Skip non-alphanumeric from right
    while (left < right && !isAlphanumeric(s[right])) right--;

    if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;

    left++;
    right--;
  }

  return true;
}

function isAlphanumeric(c) {
  return /[a-zA-Z0-9]/.test(c);
}

Dry run: isPalindrome("race a car")

left=0 'r', right=9 'r'. Match. left=1, right=8.
left=1 'a', right=8 'a'. Match. left=2, right=7.
left=2 'c', right=7 ' '. Skip right: right=6 'c'. Match. left=3, right=5.
left=3 'e', right=5 'a'. 'e' ≠ 'a' → return false. ✓

Why O(n): Each character is visited at most once. Both pointers move monotonically toward center — total moves ≤ n.

Part 5: Pattern A — Three Sum

Problem: Find all unique triplets in an unsorted array that sum to zero.
threeSum([-1, 0, 1, 2, -1, -4]) → [[-1,-1,2],[-1,0,1]]
LeetCode 15. One of the most asked interview problems globally.

Four Questions

Q1: What do I have? An array of integers. May contain duplicates. No sort guarantee.
Q2: What do I want? All unique triplets (a, b, c) where a + b + c = 0, no duplicate triplets.
Q3: What is the brute force? Triple nested loop. O(n³). Check every combination, filter sums to 0, deduplicate.
Q4: Where is the waste? For a fixed first element a, we need b + c = -a in the rest of the array. If the rest is sorted, two-pointer solves this in O(n). So: sort once, then for each element, two-pointer the rest.

The Reduction

Three Sum reduces to: for each element a at index i, run Two Sum on the sorted subarray to the right of i with target -a.

function threeSum(nums) {
  nums.sort((a, b) => a - b);  // sort once: O(n log n)
  const result = [];

  for (let i = 0; i < nums.length - 2; i++) {
    // Skip duplicate values for the first element
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let left = i + 1;
    let right = nums.length - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        // Skip duplicates for second and third elements
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }

  return result;
}

Dry Run: threeSum([-1, 0, 1, 2, -1, -4])

Step 1: Sort.
[-4, -1, -1, 0, 1, 2]

Step 2: i=0, nums[0]=-4. target for two-sum = 4.

left=1(-1), right=5(2). sum=-4-1+2=-3 < 0 → left=2.
left=2(-1), right=5(2). sum=-4-1+2=-3 < 0 → left=3.
left=3(0), right=5(2). sum=-4+0+2=-2 < 0 → left=4.
left=4(1), right=5(2). sum=-4+1+2=-1 < 0 → left=5.
left=5 >= right=5. Inner loop ends.

No triplets with nums[0]=-4.

Step 3: i=1, nums[1]=-1. target=1.

left=2(-1), right=5(2). sum=-1-1+2=0 ✓
  push [-1,-1,2].
  nums[left+1]=nums[3]=0 ≠ nums[2]=-1. No skip.
  nums[right-1]=nums[4]=1 ≠ nums[5]=2. No skip.
  left=3, right=4.
left=3(0), right=4(1). sum=-1+0+1=0 ✓
  push [-1,0,1].
  left=4, right=3.
left=4 >= right=3. Inner loop ends.

Step 4: i=2, nums[2]=-1. BUT nums[2] === nums[1] → skip (duplicate i).

Step 5: i=3, nums[3]=0. target=0.

left=4(1), right=5(2). sum=0+1+2=3 > 0 → right=4.
left=4 >= right=4. Inner loop ends.

Result: [[-1,-1,2],[-1,0,1]] ✓

Complexity

• Sort: O(n log n).
• Outer loop: O(n).
• Inner two-pointer: O(n) per outer loop iteration.
• Total: O(n²). Space: O(1) ignoring output.

Deduplication Logic — Why It Works

We skip nums[i] === nums[i-1] because: if we already processed i-1 with that value, we found all triplets containing that value. Running i would generate duplicates.

Same logic for left and right after finding a triplet: we advance past all equal values so we don't push the same triplet twice.

Key insight: Three Sum = sort + (for each element, Two Sum). This reduction pattern — "fix one variable, solve a simpler problem for the rest" — appears everywhere. Four Sum = fix two variables, run Two Sum. k-Sum = fix k-2 variables, run Two Sum.

Part 6: Pattern A — Container With Most Water

Problem: Given heights h[0..n-1], find two lines that form a container holding the most water.
maxArea([1,8,6,2,5,4,8,3,7]) → 49
LeetCode 11.

Water held by lines at i and j = min(h[i], h[j]) * (j - i).

Why Two Pointers?

Start with the widest possible container: left=0, right=n-1. Area = min(h[0], h[n-1]) * (n-1).

Now: should we move left or right?

Moving either pointer decreases width by 1. To increase area, we need to increase the minimum height. If h[left] < h[right], moving right inward can only decrease or maintain the minimum (the bottleneck is h[left]). So moving right cannot improve. We must move left.

If h[left] >= h[right], same logic in reverse — move right.

function maxArea(height) {
  let left = 0, right = height.length - 1;
  let max = 0;

  while (left < right) {
    const area = Math.min(height[left], height[right]) * (right - left);
    max = Math.max(max, area);

    if (height[left] < height[right]) left++;
    else right--;
  }

  return max;
}

Dry run: maxArea([1,8,6,2,5,4,8,3,7])

left=0(h=1), right=8(h=7). area=min(1,7)*8=8. max=8. h[0]<h[8] → left=1.
left=1(h=8), right=8(h=7). area=min(8,7)*7=49. max=49. h[1]>h[8] → right=7.
left=1(h=8), right=7(h=3). area=min(8,3)*6=18. max=49. h[1]>h[7] → right=6.
left=1(h=8), right=6(h=8). area=min(8,8)*5=40. max=49. h[1]>=h[6] → right=5.
left=1(h=8), right=5(h=4). area=min(8,4)*4=16. max=49. h[1]>h[5] → right=4.
left=1(h=8), right=4(h=5). area=min(8,5)*3=15. max=49. h[1]>h[4] → right=3.
left=1(h=8), right=3(h=2). area=min(8,2)*2=4. max=49. h[1]>h[3] → right=2.
left=1(h=8), right=2(h=6). area=min(8,6)*1=6. max=49. h[1]>h[2] → right=1.
left=1 >= right=1. Loop ends.

return 49. ✓

Why we don't miss the optimal: At every step, we discard either the left or right pointer's current position. We can prove we don't discard the optimal pair: if h[left] < h[right], then for any right' where left < right' < right, the pair (left, right') has area = min(h[left], h[right']) * (right'-left) ≤ h[left] * (right'-left) < h[left] * (right-left) ≤ area(left, right). So no pair with the current left can beat what we've already seen. Discarding left is safe.

Complexity: O(n) time, O(1) space.

Part 7: Pattern B — Fast / Slow Pointers

When both pointers move in the same direction, one pointer chases the other. The key: the slow pointer tracks a meaningful boundary, the fast pointer scans ahead.

Remove Duplicates from Sorted Array

Problem: Remove duplicates in-place from a sorted array. Return the number of unique elements.
removeDuplicates([1,1,2,2,3]) → returns 3, array becomes [1,2,3,_,_].

slow=0: marks the last confirmed unique position.
fast=1: scans forward.

If nums[fast] !== nums[slow]: a new unique value found.
  → slow++, nums[slow] = nums[fast].
Else: duplicate, advance fast only.

function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let slow = 0;

  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast];
    }
  }

  return slow + 1;  // slow is 0-indexed, count is slow+1
}

Dry run: removeDuplicates([1,1,2,2,3])

slow=0(val=1), fast=1(val=1). 1===1 → skip.
slow=0(val=1), fast=2(val=2). 2≠1 → slow=1, nums[1]=2. Array: [1,2,2,2,3].
slow=1(val=2), fast=3(val=2). 2===2 → skip.
slow=1(val=2), fast=4(val=3). 3≠2 → slow=2, nums[2]=3. Array: [1,2,3,2,3].
fast=5: out of bounds. Loop ends.
return slow+1 = 3. ✓

The array from index 0 to 2 is [1,2,3] — the unique elements in sorted order.

Mental model: slow is the "write head". fast is the "read head". We read ahead, and only write when we find something new.

Part 8: Pattern B — Move Zeroes

Problem: Move all zeroes to the end while maintaining the relative order of non-zero elements. In place.
moveZeroes([0,1,0,3,12]) → [1,3,12,0,0]
(Covered in Chapter 2 as a four-question example — now with the two-pointer lens.)

function moveZeroes(nums) {
  let slow = 0;  // next position to write a non-zero

  // Pass 1: write all non-zero elements to the front
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      nums[slow] = nums[fast];
      slow++;
    }
  }

  // Pass 2: fill rest with zeroes
  for (; slow < nums.length; slow++) {
    nums[slow] = 0;
  }
}

Dry run: moveZeroes([0,1,0,3,12])

Pass 1:
fast=0(0): skip.
fast=1(1): nums[0]=1. slow=1. Array: [1,1,0,3,12].
fast=2(0): skip.
fast=3(3): nums[1]=3. slow=2. Array: [1,3,0,3,12].
fast=4(12): nums[2]=12. slow=3. Array: [1,3,12,3,12].

Pass 2:
slow=3: nums[3]=0. Array: [1,3,12,0,12].
slow=4: nums[4]=0. Array: [1,3,12,0,0]. ✓

Part 9: Deriving Complexity — Why Two Pointers Is Always O(n)

Every two-pointer algorithm on a single array of length n is O(n) time.

Proof sketch:

• Each pointer starts at one end and moves monotonically toward the other (or the fast pointer only moves forward).
• A pointer never reverses direction.
• Total pointer moves ≤ n (for one pointer) or ≤ 2n (for two pointers).
• Each move does O(1) work.
• Total work ≤ O(1) × 2n = O(n).

The nested loop brute force is O(n²) because it doesn't exploit structure. Two pointers exploit the structure to make each move eliminate a provably useless region, letting us do n moves instead of n² comparisons.

The elimination argument is everything. If you can't prove that moving a pointer eliminates all possible correct answers in the discarded region, you cannot use two pointers.

Part 10: Mental Model — When to Reach for Two Pointers

Strong signals:

1. Sorted array + pair/triplet problem. The sort gives you structure. Two pointers exploit it.
2. "Find two elements where some condition holds." Especially if the condition changes monotonically as you move pointers.
3. In-place manipulation: partition, remove, deduplicate. Slow/fast pointer: slow = write head, fast = read head.
4. Palindrome / symmetric structure check. Opposite ends moving inward.
5. You have O(n²) brute force and feel like there's a smarter loop. Ask: if one pointer is fixed, can I determine which direction to move the other in O(1)?

NOT two pointers when:

1. The array is unsorted and you can't sort it (or sorting is too expensive given other constraints).
2. The condition doesn't have a monotonic structure — moving a pointer doesn't tell you anything.
3. You need all pairs (no elimination possible) — two pointers would miss answers.

Part 11: Real Systems

PostgreSQL Merge Join:
When joining two sorted tables, PostgreSQL's merge join is two pointers. Left pointer walks sorted left table, right pointer walks sorted right table. When values match, output the joined row. When left < right, advance left pointer. This gives O(n + m) join time vs O(n × m) for nested loop joins. The SQL query planner chooses merge join when both inputs are sorted on the join key.

Merge step in merge sort:
The merge() function from Chapter 4 is two pointers. l points into the left sorted array, r into the right sorted array. Advance the pointer pointing at the smaller value. Total moves = n. This is why merging two sorted arrays is O(n).

Git diff / text diff algorithms:
Comparing two versions of a file to find insertions and deletions. The Myers diff algorithm uses a two-pointer-like approach on the two sequences, advancing through matching characters and recording divergences.

Network packet deduplication:
Routers receiving packets from multiple paths remove duplicate packets. If packets are tagged with sequence numbers (sorted), a two-pointer scan over the combined stream eliminates duplicates in O(n) — the fast/slow pattern.

Two-phase commit in distributed systems:
Not two pointers per se, but the same structural idea: two cursors advancing through agreement phases across nodes. Mentioned because the mental model of "two things advancing toward a common state" generalizes beyond arrays.

Part 12: Vocabulary Map

Part 13: 5 Practice Problems

1. Trace and Predict

function f(nums) {
  let slow = 0;
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] % 2 !== 0) {
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      slow++;
    }
  }
  return slow;
}

Trace f([2, 1, 4, 3, 6, 5]). What does this function do? What does slow represent at each step? Is the relative order of odd numbers preserved? What about even numbers?

2. Find the Waste

Problem: Given a sorted array, return the squares of all elements in sorted order.
Input: [-4, -1, 0, 3, 10]
Expected: [0, 1, 9, 16, 100]

Approach A: map(x => x*x) then sort. 

What is the time complexity of Approach A? Where is the waste? Design a two-pointer approach that runs in O(n). Hint: the largest squares are at the two ends of the sorted input.

3. Failure Analysis

function threeSum(nums) {
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) result.push([nums[i], nums[left], nums[right]]);
      if (sum < 0) left++;
      else right--;
    }
  }
  return result;
}

This code has two bugs. Identify both. Hint: (1) what happens when i === left or i === right? (2) When a triplet is found, does the inner loop terminate correctly?

4. Design Under Constraints

Design a two-pointer solution for: "Given a sorted array, remove all occurrences of a specific value val in-place. Return the number of elements not equal to val."

Constraint: O(1) space. Must be in-place. The order of elements not equal to val does not matter.

Then: extend your solution to handle "remove elements equal to val that appear more than k times" (where k is given, k ≥ 1). How does the logic change?

5. Reach Beyond

trappingRainWater was solved in Chapter 2a using prefix/suffix max arrays (O(n) space). Can you solve it with two pointers in O(1) space?

Hint: if leftMax < rightMax, the water at left is determined by leftMax (the right wall is guaranteed to be taller or equal). Else, the water at right is determined by rightMax. Move the pointer on the shorter wall side.

Write the code, trace it on [0,1,0,2,1,0,1,3,2,1,2,1] (answer: 6), and prove why the elimination argument holds.

Connect Forward

Chapter 6 — Sliding Window is two pointers where both move in the same direction and define a "window" between them. The window expands by advancing the right pointer and contracts by advancing the left pointer. It is the same pattern with a different invariant: instead of converging from opposite ends, we maintain a property across a contiguous subarray.

The structural bridge: in two pointers (opposite ends), we eliminate one end when the condition fails. In sliding window (same direction), we shrink the left side when the window violates a constraint. Same mental motion, different geometry.

Connect Backward

Chapter 3a introduced Two Sum using a HashMap — O(n) time, O(n) space. Two Pointers solves Two Sum II (sorted array) in O(n) time, O(1) space. The tradeoff: HashMap works on unsorted arrays, two pointers requires sorting. Chapter 5's Three Sum sorts first (O(n log n)), then uses two pointers — combining both insights.

Chapter 4's merge sort merge() function was already two pointers. You've been using this technique; now you have the vocabulary for it.