Two Pointers

Two pointers is not one trick. It is a family of linear-time strategies where two indices encode state that would otherwise require nested loops.

If you master this topic, you convert many O(n^2) array and string problems into O(n).

The Core Principle

At every step, at least one pointer moves forward (or inward), and no pointer moves backward into already-resolved territory.

That monotonic movement gives a linear bound.

If each pointer moves at most n times, total pointer moves are at most 2n, so time is O(n).

Pointer Taxonomy (Know Which One You Are Using)

1) Opposite-direction pointers (converging)

• start at both ends
• move inward
• common on sorted arrays and palindrome-like checks

2) Same-direction pointers (read/write or left/right boundaries)

• both move left to right
• one scans, one marks valid prefix/window
• common for in-place compaction

3) Different-speed pointers (slow/fast)

• move at different rates
• common for cycle detection and midpoint logic

In interviews, explicitly naming the variant signals strong fundamentals.

Pattern 1: Converging Pointers on Sorted Data

Canonical example: Two Sum II (sorted input)

function twoSumSorted(nums: number[], target: number): number[] {
  let left = 0
  let right = nums.length - 1

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

Why movement is correct (proof sketch)

Suppose sum < target at (left, right) in a sorted array.

• Keeping left fixed and moving right left can only decrease (or keep) sum.
• So no pair with this left and any smaller right can reach target.
• Therefore left is safe to discard; move left++.

Symmetric argument for sum > target and right--.

This elimination argument is the reason we can skip O(n) candidates safely each step.

Template

let l = 0
let r = arr.length - 1

while (l < r) {
  // evaluate arr[l], arr[r]
  if (/* good */) return ...
  if (/* need larger */) l++
  else r--
}

Advanced Converging Variant: 3Sum

3Sum is the first “real” test of two-pointer maturity.

Idea:

1. sort array
2. fix one index i
3. run 2-pointer on suffix [i+1 ... n-1]
4. handle duplicates carefully

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b)
  const result: number[][] = []

  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue // dedup anchor
    if (nums[i] > 0) break // sorted: no future triplet can sum to 0

    let l = i + 1
    let r = nums.length - 1

    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r]
      if (sum === 0) {
        result.push([nums[i], nums[l], nums[r]])
        l++
        r--
        while (l < r && nums[l] === nums[l - 1]) l++ // dedup left
        while (l < r && nums[r] === nums[r + 1]) r-- // dedup right
      } else if (sum < 0) {
        l++
      } else {
        r--
      }
    }
  }
  return result
}

Complexity:

• sorting: O(n log n)
• scan with pointers: O(n^2)
• total: O(n^2)

Pattern 2: Same-Direction Read/Write Pointers

Use when problem asks for in-place modification with O(1) extra space.

Example A: remove duplicates from sorted array

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0

  let write = 1
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[read - 1]) {
      nums[write] = nums[read]
      write++
    }
  }
  return write
}

Invariant:

• before each step, nums[0..write-1] is deduplicated and valid
• read scans unseen region

Example B: move zeroes

function moveZeroes(nums: number[]): void {
  let write = 0
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      ;[nums[write], nums[read]] = [nums[read], nums[write]]
      write++
    }
  }
}

Why swap works:

• write tracks first zero slot in prefix
• when non-zero appears at read, swap it forward
• prefix [0..write-1] remains all non-zero

Pattern 3: Symmetry / Palindrome Pointers

Check pairs from both ends; skip irrelevant chars if needed.

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

function isPalindrome(s: string): boolean {
  let l = 0
  let r = s.length - 1

  while (l < r) {
    while (l < r && !isAlphanumeric(s[l])) l++
    while (l < r && !isAlphanumeric(s[r])) r--
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false
    l++
    r--
  }
  return true
}

Common extension: “valid palindrome II” where you may delete at most one char.

Pattern 4: Slow/Fast Pointers (Different Speed)

Linked-list cycle detection (Floyd)

type Node = { val: number; next: Node | null }

function hasCycle(head: Node | null): boolean {
  let slow = head
  let fast = head
  while (fast && fast.next) {
    slow = slow!.next
    fast = fast.next.next
    if (slow === fast) return true
  }
  return false
}

Intuition:

• in a cycle, fast gains one node per step over slow
• finite cycle length means fast must eventually lap slow

Array variant: find duplicate number (value-as-next-index graph)

If values are in [1..n], treat nums[i] as next pointer and detect cycle entry.

This is a high-signal interview pattern showing you can abstract beyond raw arrays.

Two Pointers vs Sliding Window

They are related but not identical.

Quick rule:

• if both ends matter -> two pointers
• if contiguous validity over changing range matters -> sliding window

When NOT to Use Two Pointers

1. Unsorted pair-sum where original indices matter and sorting is disallowed -> hashmap
2. Non-contiguous selection problems -> DP/backtracking, not pointers
3. Constraints that are not monotonic under pointer movement -> two pointers may break
4. String problems requiring global frequency but not order -> counter/map approach first

Two pointers is powerful only when pointer movement can safely discard candidates.

Edge Cases Checklist

Before finalizing:

• empty input ([], "")
• single element
• all duplicates
• already optimal / already invalid
• large negatives and positives
• overflow in non-JS languages when summing
• dedup loops after pointer move (3Sum especially)
• pointer crossing conditions (l < r vs l <= r)

Most bugs come from missing one of these, not from algorithm choice.

Interview Communication Script (Use This Verbatim Style)

1. “Input is sorted, so if sum is too small I must move left rightward.”
2. “This discards all pairs with current left safely.”
3. “Each pointer moves at most n times, so total O(n), space O(1).”

Clear elimination reasoning earns more credit than just code.

Problem Ladder (Suggested Mastery Path)

Easy

• Valid Palindrome
• Reverse String
• Remove Duplicates from Sorted Array
• Move Zeroes

Medium

• Two Sum II
• 3Sum
• Container With Most Water
• Sort Colors (Dutch National Flag)

Hard-ish / signal boosters

• Trapping Rain Water
• 4Sum
• Find the Duplicate Number (Floyd cycle mapping)

Complexity Summary

Even when a while sits inside a for (3Sum inner scan), pointer monotonicity keeps each scan linear per anchor.

Final Takeaway

Two pointers is an elimination framework:

• define what each pointer represents
• define movement rule
• justify why moved-away states can never be optimal/valid

If you can state those three clearly, you can solve most pointer problems under pressure with confidence.