Day 4: Two-Pointer Pattern

DAY 4 / 30 · WEEK 1

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

Sorted array: [2, 4, 5, 7, 9], target = 12

Press Play or Step to begin.

Step 0 / 8

2. Remove Duplicates — read/write pointers

Array with duplicates: [1, 1, 2, 2, 2, 3, 4, 4]

Press Play or Step to begin.

Step 0 / 9

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)

Step	left	right	nums[left] + nums[right]	Action
1	0 (2)	4 (9)	11	too small → left++
2	1 (4)	4 (9)	13	too big → right–
3	1 (4)	3 (7)	11	too small → left++
4	2 (5)	3 (7)	12	match! return [2, 3]

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])

read	nums[read]	nums[write]	Action	write after
1	1	1 (write=0)	same → duplicate, skip	0
2	2	1 (write=0)	different → write++, copy	1
3	2	2 (write=1)	same → duplicate, skip	1
4	3	2 (write=1)	different → write++, copy	2

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

Approach	Time	Space	Why
Brute-force pair check (nested loop)	O(n²)	O(1)	Every element compared against every other element.
Two-pointer, converging	O(n)	O(1)	Each pointer only ever moves inward — at most n moves total, combined.
Two-pointer, read/write	O(n)	O(1)	A single pass; write only touches each output slot once.

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.

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

1. Remove Duplicates from Sorted Array

Easy — LeetCode: Remove Duplicates from Sorted Array

Remove duplicates from a sorted array in place so each unique element appears once, and return the count of unique elements.

Show hint

This is exactly today’s read/write pattern. Compare each element to the last one you wrote, not the last one you read.

Show solution

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;
}

2. Two Sum II - Input Array Is Sorted

Medium — LeetCode: Two Sum II - Input Array Is Sorted

Given a sorted array and a target, return the 1-indexed positions of the two numbers that add up to the target.

Show hint

This is exactly today’s converging pattern — the only twist is the answer is 1-indexed, not 0-indexed.

Show solution

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];
}

3. Container With Most Water

Medium — LeetCode: Container With Most Water

Given heights of vertical lines, find two lines that, together with the x-axis, form a container holding the most water.

Show hint

Start with the widest possible container (both ends) and always move the pointer at the shorter wall inward — see the Interview Corner for why that’s the only move that can improve the answer.

Show solution

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

The converging two-pointer pattern for pair-sum problems requires the array to be:
- Sorted ✓
- All unique values
- Any array works
In the converging pattern, if the current sum is LESS than the target, which pointer moves?
- left (moves forward) ✓
- right (moves backward)
- Both pointers
In the read/write pointer pattern for removing duplicates, what does the write pointer represent?
- The boundary of the unique section built so far ✓
- The element currently being read
- The target value being searched for
What’s the time complexity of the two-pointer approach, versus a brute-force nested-loop pair check?
- O(n) vs O(n²) ✓
- O(log n) vs O(n)
- They’re the same complexity
In Container With Most Water, which pointer should you move inward?
- The pointer at the shorter wall ✓
- The pointer at the taller wall
- It never matters which one