Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Sliding Window
  • Two Pointers
  • Prefix Sum & Hash Map
  • Cyclic Sort
  • Merge Intervals
  • Monotonic Stack
Learn/Data Structures & Algorithms/Arrays & Strings

Two Pointers

7 min Beginner 8 steps

Walk inward from both ends of a sorted array in one pass.

target
6
sum
3
Pairs checked
1up to n²/2
0123412346ij
current done skipped
In this lessonStep 1 of 8
  1. The problem
  2. Both ends
  3. Two Sum
  4. Container
  5. Read/write
  6. Partition
  7. Sort first?
  8. Recap
Step 1 / 8problem

Checking every pair

Find two numbers in the sorted array [1, 2, 3, 4, 6] that add up to 6.

Trying every pair works, but it ignores the fact that the array is sorted and costs O(n²) in the worst case.

Key idea

Sorted input plus "find a pair" is the classic signal for two pointers.

←→ step·R replay·Space pause

You'll learn

  • Replace an O(n²) pair search with one inward pass
  • Justify every pointer move by the pairs it rules out
  • Compact an array in place with read and write pointers
  • Partition into three regions with the Dutch national flag
  • Know when sorting first is worth it
Read the full notesArrays and Linked Lists, 3