Skip to content
ComplexityX

Settings

Server engine

Loading…

Use my own key optional

The key stays in this browser's local storage and is sent only to this app's /api/analyze route, which forwards it to the provider. It is never stored on the server.

All patterns

Two Pointers

Walk two indices through the data so nothing is scanned twice.

time O(n) after sortingspace O(1)

What it is

Keep two indices, usually at opposite ends or moving in the same direction, and move them by rule instead of testing every pair. Each pointer only moves one way, so the total work is linear.

When to reach for it

  • Sorted array or string and you need a pair, triple or partition
  • In-place removal, dedupe or reordering
  • Palindrome or symmetric checks
  • Merging two sorted sequences

Clues in the problem

  • “Find two numbers that…” on sorted input
  • Asked for O(1) extra space
  • Brute force is a nested loop over i < j

Template

def two_pointers(a, target):
lo, hi = 0, len(a) - 1
while lo < hi:
s = a[lo] + a[hi]
if s == target:
return lo, hi
if s < target:
lo += 1 # need a bigger sum
else:
hi -= 1 # need a smaller sum
return None

Practice problems

  • Two Sum II (sorted)
  • 3Sum
  • Container With Most Water
  • Remove Duplicates from Sorted Array
  • Valid Palindrome

Common mistakes

  • Using it on unsorted data without sorting first
  • Moving both pointers when only one should move
  • Off-by-one on lo < hi versus lo <= hi