2.1 Two Pointers

1. What Is the Two Pointers Technique?

In array problems, a "pointer" is simply an integer variable (like left = 0 or right = n - 1) that remembers a position in the array.

Instead of using a single loop variable i (which only looks at one spot at a time) or two nested loops for i ... for j ... (which blindly checks every pair in O(N^2) time), Two Pointers places two coordinated bookmarks in the array and moves them using a smart rule so each element is visited at most once (O(N) time) with O(1) extra space.

2. Why Do We Need Two Pointers & How Do the 3 Flavors Work?

Flavor 1: Opposite-End Pointers (left = 0, right = n - 1)

Suppose you have a sorted list [2, 5, 8, 12, 30, 45] and want two numbers that add up to 35. If you stand at left = 0 (2) and right = 5 (45):

• 2 + 45 = 47 (too big!). Since 2 is already the smallest number in the list, 45 added to anything else will be even bigger than 47. We can permanently cross out 45 (right -= 1)!
• Now 2 + 30 = 32 (too small!). Since 30 is the largest remaining number, 2 is too small for everything else. Cross out 2 (left += 1)!
• Now 5 + 30 = 35 — found in 3 steps instead of N^2!

Flavor 2: Same-Direction Read / Write Pointers (write = 0, read = 0)

When you need to filter or compact an array in-place (like removing duplicates or moving zeroes to the end), calling nums.pop(i) shifts the whole array (O(N^2)). Instead, read scans every element while write marks the next clean slot. Whenever read finds a keeper, copy nums[read] to nums[write] and step write += 1.

Flavor 3: Three-Way Partitioning (low, mid, high)

When sorting an array with only 3 distinct values (0, 1, 2 in Sort Colors), keep 0s before low, 1s between low and mid, and 2s after high.

Step Through the Visual Drawing: Converging Two Pointers

Click Next below to see why moving left++ or right-- eliminates an entire row of pairs in O(1) time:

3. Basic Operations & Walkthroughs (All 4 Languages)

# 1. Opposite-End Pointers: Valid Palindrome / Sorted Two-Sum
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
  left, right = 0, len(nums) - 1
  while left < right:
      s = nums[left] + nums[right]
      if s == target:
          return [left + 1, right + 1]
      elif s < target:
          left += 1
      else:
          right -= 1
  return []

# 2. Same-Direction Read/Write: Remove Duplicates from Sorted Array
def remove_duplicates(nums: list[int]) -> int:
  write = 1
  for read in range(1, len(nums)):
      if nums[read] != nums[write - 1]:
          nums[write] = nums[read]
          write += 1
  return write

# 3. Three-Way Partitioning (Sort Colors 0, 1, 2)
def sort_colors(nums: list[int]) -> None:
  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] == 1:
          mid += 1
      else:
          nums[mid], nums[high] = nums[high], nums[mid]
          high -= 1

4. Core Interview Patterns & Common Traps

nums.sort()
for i in range(len(nums) - 2):
  if i > 0 and nums[i] == nums[i - 1]:
      continue  # Skip duplicate anchor
  l, r = i + 1, len(nums) - 1
  while l < r:
      s = nums[i] + nums[l] + nums[r]
      if s == 0:
          res.append([nums[i], nums[l], nums[r]])
          l += 1; r -= 1
          while l < r and nums[l] == nums[l - 1]: l += 1
      elif s < 0: l += 1
      else: r -= 1

5. Practice On Your Own (Curated Submodule Problems)