DAY 4 / 30 · WEEK 1

Two-Pointer Pattern

Goal of the day

• Recognize when a problem is a good fit for two pointers — usually a sorted array, or "compare pairs" phrasing.
• Implement both common shapes: pointers converging from opposite ends, and pointers moving the same direction at different speeds.
• Turn an O(n²) brute-force pair search into an O(n) two-pointer scan.

Concept

Picture two librarians searching a sorted shelf for two books whose page counts add up to exactly 500. Instead of checking every possible pair (that's the brute-force O(n²) way), one librarian starts at the thinnest book, the other at the thickest, and they walk toward each other. If the two page counts add up to too much, the one at the thick end steps in (a smaller book). If it's too little, the one at the thin end steps in (a bigger book). Every step rules out one book from further consideration — that's what makes it O(n) instead of O(n²). This only works because the shelf is sorted; on a shuffled shelf, moving a pointer wouldn't reliably move the sum in a useful direction.

The second shape is different: two pointers moving the same direction, one fast (scanning ahead) and one slow (marking where to write next). This is how you compact an array in place — for example, squeezing out duplicates from a sorted array without allocating a new one. You saw this exact "read pointer / write pointer" idea already in Day 3's String Compression problem — two-pointer isn't one trick, it's a family of tricks that all avoid a nested loop.

Diagrams

1. Converging pointers (opposite ends)

2. Same-direction pointers (read / write)

Interactive visualizations

1. Two Sum II — converging pointers

2. Remove Duplicates — read/write pointers

The code

// --- Shape 1: converging pointers (array must be SORTED) ---
function twoSumSorted(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;   // need a bigger sum → drop the smaller number
    else right--;               // need a smaller sum → drop the bigger number
  }
  return [-1, -1]; // no pair found
}

// --- Shape 2: same-direction read/write pointers ---
function removeDuplicates(nums) {
  let write = 0; // boundary of the unique section built so far; nums[0] is already "written"
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write]) {
      write++;
      nums[write] = nums[read];
    }
  }
  return write + 1; // length of the deduplicated section
}

Line by line:

• twoSumSorted — left and right start at the two ends. Each loop compares the current sum to the target and moves exactly one pointer inward — never both, and never outward. That guarantees at most n total moves.
• removeDuplicates — nums[0] is trivially already "written," so read starts at index 1 and visits every remaining index once. write only moves (and copies nums[read] into the array) when it spots a genuinely new value — so duplicates are simply never copied forward.

Dry run: twoSumSorted([2, 4, 5, 7, 9], target = 12)

Found in 4 steps instead of checking all 5×4/2 = 10 possible pairs — and this same array/target pair is what the interactive visualization above animates.

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

Returns write + 1 = 3 — the first 3 slots, [1, 2, 3], are the deduplicated result. This matches Diagram 2 above at the moment read=4: write is still at index 1, about to become 2.

Complexity

Interview corner

• How do you know a problem is a two-pointer fit? Look for: the array is sorted (or can cheaply be sorted), you're comparing pairs or a range, and a brute-force solution would be O(n²) with two nested loops over the same array.
• Why does the converging pattern require a sorted array? The decision "move left or move right" relies on knowing that increasing left can only increase the sum, and decreasing right can only decrease it. That's only guaranteed if the array is sorted.
  ⚠ Trap: running this pattern on unsorted data doesn't crash — it just silently returns a wrong or missed answer, the same class of bug as running binary search on unsorted data. Always confirm "is this sorted?" before reaching for converging two pointers.
• What if there could be multiple valid pairs? Don't return immediately on a match — record it and keep moving both pointers inward (skipping over duplicate values if the problem asks for unique pairs).
  ↳ Common follow-up: "Now do it for triplets" (3Sum) — fix one pointer, run the two-pointer scan on the rest. Same core idea, one extra outer loop.
• In Container With Most Water, why move the shorter wall's pointer, not the taller one's? The container's height is capped by the shorter wall. Moving the taller wall's pointer inward can only shrink the width while the height cap stays the same or gets worse — it can never help. Moving the shorter wall is the only move that has any chance of finding a taller wall and improving the area.

How to talk through it out loud: state the precondition first — "since this array is sorted, I can use two pointers converging from both ends instead of checking every pair" — then narrate each pointer move in terms of the goal: "the sum's too small, so I need a bigger number, so I'll move left forward." Naming why a pointer moves, not just that it moves, is what shows you understand the pattern instead of having memorized it.

Practice problems

function removeDuplicates(nums) {
  let write = 0; // nums[0] is already "written"
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write]) {
      write++;
      nums[write] = nums[read];
    }
  }
  return write + 1;
}

function twoSum(numbers, target) {
  let left = 0, 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++;
    else right--;
  }
  return [-1, -1];
}

function maxArea(height) {
  let left = 0, right = height.length - 1;
  let best = 0;
  while (left < right) {
    const width = right - left;
    const area = width * Math.min(height[left], height[right]);
    best = Math.max(best, area);
    if (height[left] < height[right]) left++;
    else right--;
  }
  return best;
}

Quiz