Algorithms & Coding Interviews · Arrays, Strings & Linear Structures

Two Pointers

Two pointers turn an O(n²) scan over pairs into one O(n) pass by exploiting order. Learn why moving one pointer is always safe, the opposite-end and same-direction templates, and watch six LeetCode problems, from Two Sum II to Trapping Rain Water, solved step by step.

🧮 Algorithms & Coding Interviews● Beginner⏱ 9 min read▶ 4 interactive🛠️ 4 exercises

🎯 What you'll learn

Opposite-end vs same-direction pointers
Why each step safely discards a candidate
k-Sum, duplicate skipping and the Dutch national flag
Six LeetCode problems with animated walkthroughs

📚 Before you start

Arrays & hashing

Part 1The Pattern

Two pointers replace a nested loop over pairs with one coordinated scan. It works whenever the data has an order you can exploit: a sorted array (move the pointer that brings you closer to the goal), or a single pass where one pointer reads and the other writes. Both pointers only move forward (or inward), so the total work is O(n).

Opposite-end pointers on a sorted array moving inward based on the current sum

1The Two Shapes

Shape	Pointers	Typical problems
Opposite ends	`left = 0`, `right = n − 1`, move inward	pair sum in sorted array, palindromes, container with most water, 3Sum (after sorting)
Same direction	`slow`/`fast` or `write`/`read`, both move right	remove duplicates, move zeroes, partitioning, merge sorted arrays, linked-list cycle

2Why Moving One Pointer Is Safe

On a sorted array with sum = a[left] + a[right]:

If sum < target, every pair using a[left] with any index ≤ right is also too small (they're all ≤ a[right]). So a[left] can never be part of the answer: discard it with left += 1.
If sum > target, symmetrically a[right] is too big for every remaining partner: right -= 1.

Each step eliminates a whole row or column of the n×n pair matrix, which is why n steps are enough. Being able to say this out loud is what interviewers want to hear.

3Templates

typescript

function pairWithSum(nums: number[], target: number): number[] {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const s = nums[left] + nums[right];
    if (s === target) return [left, right];
    if (s < target) left++; else right--;
  }
  return [];
}

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

python

def pair_with_sum(nums, target):          # nums is sorted
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        if s < target:
            left += 1                       # need a bigger sum
        else:
            right -= 1                      # need a smaller sum
    return []

def compact(nums):                         # same-direction: read / write pointers
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:                 # keep condition
            nums[write] = nums[read]
            write += 1
    return write                            # new logical length

4Recognition Cues

The input is sorted, or sorting it doesn't break the problem (you only need values, not original indices).
"Find a pair/triplet with property X", "closest sum", "count pairs less than target".
"In place", "O(1) extra space", "remove/move elements while keeping order".
Symmetry: palindromes, reversing, comparing from both ends.

If you need original indices from an unsorted array, sorting loses them: prefer a hash map (Two Sum) or sort pairs (value, index).

5Variations

k-Sum: sort once, fix the first k − 2 elements with loops, finish with two pointers. 3Sum is O(n²), 4Sum O(n³).
Skipping duplicates: after using a value, advance while the next value is the same, to avoid duplicate triplets.
Three pointers (Dutch national flag): low, mid, high partition an array into three groups in one pass (Sort Colors).
Fast and slow on linked lists: Floyd's cycle detection and finding the middle node (see 08-linked_lists).

⚠️ Common Pitfalls

left <= right vs left < right: for pairs, the pointers must not meet (an element can't pair with itself).
Infinite loops: every branch must move at least one pointer.
Duplicate results in k-Sum: skip equal values after recording an answer, and when choosing the fixed element.
Sorting when indices are required: you lose the original positions.
Off-by-one on the write pointer: write is the next free slot, so the kept length is write, not write + 1.

📋 Quick Reference

text

Opposite: l=0, r=n-1; while l<r: s<t → l++ ; s>t → r-- ; else answer
Same-dir: write=0; for read…: if keep(a[read]): a[write]=a[read]; write++
k-Sum: sort; fix first k-2; two pointers on the rest; skip duplicates
Time O(n) after sorting (O(n log n) total if you sort) · Space O(1)

Part 2Interview Problems

Six problems covering both shapes: opposite ends (sorted pairs, containers, rain water) and same direction (in-place compaction, partitioning).

1Two Sum II – Input Array Is Sorted (LeetCode 167)

🟠 Medium. numbers is sorted ascending. Return the 1-indexed positions [i, j] of the two numbers adding up to target. Use O(1) extra space.

text

numbers = [2,7,11,15], target = 9 → [1,2]

Approach. Opposite-end pointers: too small → move left right; too big → move right left.

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

typescript

function twoSumSorted(numbers: number[], target: number): number[] {
  let left = 0, right = numbers.length - 1;
  while (left < right) {
    const s = numbers[left] + numbers[right];
    if (s === target) return [left + 1, right + 1];
    if (s < target) left++; else right--;
  }
  return [];
}

python

def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]
        if s < target:
            left += 1
        else:
            right -= 1
    return []

2Move Zeroes (LeetCode 283)

🟢 Easy. Move all zeros to the end of nums in place, keeping the relative order of the non-zero elements.

text

nums = [0,1,0,3,12] → [1,3,12,0,0]

Approach. Read/write pointers: copy every non-zero to write and advance it; then fill the rest with zeros. (A swap-based version does it in one pass.)

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

typescript

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

python

def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

33Sum (LeetCode 15)

🟠 Medium. Return all unique triplets [a, b, c] from nums with a + b + c = 0.

text

nums = [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]]

Approach. Sort. For each index i (skipping duplicate values), run two pointers on the rest looking for −nums[i]. After finding a triplet, move both pointers and skip equal values so no triplet repeats. Stop early once nums[i] > 0.

Complexity. O(n²) time, O(1) extra space besides the output (sorting may use O(n)).

typescript

function threeSum(input: number[]): number[][] {
  const nums = [...input].sort((a, b) => a - b);
  const res: number[][] = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) break;
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const s = nums[i] + nums[left] + nums[right];
      if (s < 0) left++;
      else if (s > 0) right--;
      else {
        res.push([nums[i], nums[left], nums[right]]);
        left++; right--;
        while (left < right && nums[left] === nums[left - 1]) left++;
      }
    }
  }
  return res;
}

python

def three_sum(nums):
    nums = sorted(nums)
    res = []
    for i in range(len(nums) - 2):
        if nums[i] > 0:
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s < 0:
                left += 1
            elif s > 0:
                right -= 1
            else:
                res.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
    return res

4Container With Most Water (LeetCode 11)

🟠 Medium. height[i] is a vertical line at x = i. Pick two lines that, with the x-axis, hold the most water; return that area.

text

height = [1,8,6,2,5,4,8,3,7] → 49

Approach. Start with the widest container (left = 0, right = n − 1). The area is limited by the shorter line, so moving the taller line inward can only shrink the width without raising the limit. Always move the shorter one.

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

typescript

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

python

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        best = max(best, (right - left) * min(height[left], height[right]))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

5Trapping Rain Water (LeetCode 42)

🔴 Hard. Given bar heights, compute how much rainwater is trapped between them.

text

height = [0,1,0,2,1,0,1,3,2,1,2,1] → 6

Approach. Water above bar i = min(maxLeft, maxRight) − height[i]. With two pointers, keep leftMax and rightMax. Whichever side has the smaller max is the bottleneck, and that side's water is known exactly (the other side has at least that tall a wall). Process that side and move inward.

Complexity. O(n) time, O(1) space (versus O(n) space for the prefix-max/suffix-max arrays solution).

typescript

function trap(height: number[]): number {
  let left = 0, right = height.length - 1, leftMax = 0, rightMax = 0, water = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left++];
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right--];
    }
  }
  return water;
}

python

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = water = 0
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water

6Sort Colors (LeetCode 75)

🟠 Medium. Sort an array of 0s, 1s and 2s in place in one pass (no library sort).

text

nums = [2,0,2,1,1,0] → [0,0,1,1,2,2]

Approach. Dutch national flag with three pointers: everything before low is 0, everything after high is 2, mid scans. A 0 swaps to low (both advance), a 2 swaps to high (only high moves, because the swapped-in value hasn't been examined), a 1 just advances mid.

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

typescript

function sortColors(nums: number[]): void {
  let low = 0, mid = 0, high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] === 0) { [nums[low], nums[mid]] = [nums[mid], nums[low]]; low++; mid++; }
    else if (nums[mid] === 2) { [nums[mid], nums[high]] = [nums[high], nums[mid]]; high--; }
    else mid++;
  }
}

python

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 2:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
        else:
            mid += 1

🧠 Key takeaways

Two pointers need an order to exploit: sorted data or a read/write scan.
On sorted pairs, the pointer you move is the one that can't be in any answer.
Each pointer moves at most n times → O(n); add O(n log n) if you sort first.
k-Sum = sort + fixed loops + two pointers; skip duplicates to keep results unique.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_two_pointers_exercise_1.py

TS PY

algo_two_pointers_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. In Two Sum II, sum < target. Which pointer moves?

a[left] is too small for every partner.

2. Container With Most Water moves the shorter line because…

Width shrinks either way.

3. 3Sum time complexity with sorting + two pointers?

n fixed elements × O(n) scan.

4. In Sort Colors, after swapping a 2 to high, why doesn't mid advance?

Unknown value at mid.

Source: algo_two_pointers_theory_1.md, algo_two_pointers_theory_2.md · generated by tools/build_lessons.py