Knowledge Guide
Home › DSA

Two Pointers

Step 3 in the DSA path · 1 concepts · 4 problems

0 / 5 complete

📘 Learn Two Pointers from zero

The Two Pointers pattern walks two indices through a data structure—usually from opposite ends or at different speeds—so you replace a brute-force O(n²) double loop with a single O(n) sweep using O(1) extra space. The classic trigger: a sorted array (or string/linked list) where you must find a pair, triplet, or subarray that satisfies a condition. Because the data is sorted, comparing the current pair against the target tells you which direction to move, so you never waste a comparison. Canonical example: Pair with Target Sum — given a sorted array and a target, return the indices of two numbers that add up to it.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — Setup: place pointers at both ends

Problem: sorted arr = [1, 2, 4, 6, 8, 9, 14, 15], target = 13. We anchor L at the smallest value (index 0) and R at the largest (index 7).

idx:   0   1   2   3   4   5   6   7
arr: [ 1   2   4   6   8   9  14  15 ]
       ^                           ^
       L                           R

L=0  R=7   sum = 1 + 15 = 16   target = 13

The window [L..R] spans the full array, so the true pair (if any) is guaranteed to lie inside it. This invariant is what makes shrinking safe.

Step 2 — Sum too big, move R inward

sum = 1 + 15 = 16 > 13. The sum is too large. Since the array is sorted, the only way to decrease the sum is to drop the largest element, so we move R left: R: 7 → 6.

idx:   0   1   2   3   4   5   6   7
arr: [ 1   2   4   6   8   9  14  15 ]
       ^                       ^
       L                       R

L=0  R=6   sum = 1 + 14 = 15   target = 13

Why safe: 15 paired with anything ≥ arr[L] only gets bigger, so 15 can never be part of the answer. Discarding it loses no valid pair.

Step 3 — Still too big, move R again

sum = 1 + 14 = 15 > 13. Still too large. Same rule: shrink from the right. R: 6 → 5.

idx:   0   1   2   3   4   5   6   7
arr: [ 1   2   4   6   8   9  14  15 ]
       ^                   ^
       L                   R

L=0  R=5   sum = 1 + 9 = 10   target = 13

Why safe: 14 was the largest remaining value; if even 1 + 14 overshoots, no smaller left value will rescue it. We retire 14 permanently.

Step 4 — Sum too small, move L outward

sum = 1 + 9 = 10 < 13. Now the sum is too small. To increase it we must abandon the smallest element, so we move L right: L: 0 → 1.

idx:   0   1   2   3   4   5   6   7
arr: [ 1   2   4   6   8   9  14  15 ]
           ^               ^
           L               R

L=1  R=5   sum = 2 + 9 = 11   target = 13

Why safe: 1 is the smallest value left; paired with the largest available (9) it still falls short, so 1 cannot reach the target with any element ≤ arr[R]. Drop it.

Step 5 — Still too small, move L again

sum = 2 + 9 = 11 < 13. Still short. Increase the sum by advancing L again: L: 1 → 2.

idx:   0   1   2   3   4   5   6   7
arr: [ 1   2   4   6   8   9  14  15 ]
               ^           ^
               L           R

L=2  R=5   sum = 4 + 9 = 13   target = 13

Why safe: 2 paired with the current largest candidate (9) is the best 2 could ever do here and it still misses, so 2 is exhausted. The pointers have not crossed, so a solution may still exist.

Step 6 — Match found, return indices

sum = 4 + 9 = 13 == target. The pair is found. Return the indices [L, R] = [2, 5].

idx:   0   1   2   3   4   5   6   7
arr: [ 1   2   4   6   8   9  14  15 ]
               ^           ^
               L           R
             FOUND ----- FOUND

4 + 9 = 13  ->  answer = [2, 5]

Each step moved exactly one pointer one slot, so across the whole run L and R together traverse the array at most once: O(n) time, O(1) space.

Step 7 — Termination & the no-solution case

The loop condition is while (L < R). If the pointers meet without a match, every candidate pair has been ruled out and we return [-1, -1]. Example: same array with target = 100. Every sum stays below 100, so L keeps advancing until it reaches R:

idx:   0   1   2   3   4   5   6   7
arr: [ 1   2   4   6   8   9  14  15 ]
                           ^   ^
                           L   R   (L < R, sum = 14 + 15 = 29 < 100, move L)
                               ^
                              L=R=7   <- pointers met, STOP

no pair sums to 100  ->  return [-1, -1]

Why correct: every move discards exactly one element that provably cannot be in any answer, so when the search space collapses (L == R) we have safely eliminated all O(n²) pairs in only n steps.

🎯 Guided practice

  1. Easy — Squares of a Sorted Array. Given a sorted array that may contain negatives, e.g. [-4, -1, 0, 3, 10], return the squares in sorted order. Naive: square everything then sort → O(n log n). Two-pointer reasoning: after squaring, the largest values come from the two ends (a large-magnitude negative squares to a large number). So put left=0, right=n-1, and fill a result array from the back. Compare arr[left]*arr[left] vs arr[right]*arr[right]: whichever square is bigger goes into the current highest empty slot, then advance that pointer inward. Step: (-4)²=16 vs 10²=100 → place 100 at the end, move right in. Continue until the pointers cross. Result [0,1,9,16,100] in O(n) time, O(n) output space. Core lesson: opposite-ends pointers exploit the fact that the extremes carry the answer.
  2. Medium — Dutch National Flag (sort 0s, 1s, 2s). Given [2, 0, 2, 1, 1, 0], sort in place in one pass. Three pointers: low = boundary of the known-0s region, high = boundary of the known-2s region, mid = current scanner. Invariant: everything before low is 0, everything after high is 2, and [low..mid) is all 1s. Loop while mid <= high: if arr[mid]==0, swap with arr[low], then low++, mid++. If arr[mid]==1, just mid++. If arr[mid]==2, swap with arr[high], then high-- but do NOT advance mid (the value pulled in from high hasn't been inspected yet — the classic pitfall). Trace: mid=0 sees 2 → swap with index 5 → [0,0,2,1,1,2], high=4; now mid=0 sees 0 → swap with low (itself), low=1,mid=1; continue until sorted [0,0,1,1,2,2]. O(n) time, O(1) space. Core lesson: multiple pointers can maintain region invariants to partition in a single sweep.

✨ Added by the guide — work these before the full problem set.

Lessons in this topic