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

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.
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

○Introduction to Two Pointers Pattern
○easy Pair with Target Sum
○medium Dutch National Flag Problem
○medium Comparing Strings containing Backspaces
○medium Minimum Window Sort

🧠 Review & recall

Active recall is what moves a topic into long-term memory. Flip each card before revealing, then test yourself — your results are saved on this device.

Flashcard

What problem signals tell you to reach for the Two Pointers pattern?

tap to reveal →

Two Pointers is useful when you deal with a sorted array (or linked list) and need to find a set of elements that fulfill certain constraints — the set could be a pair, a triplet, or a subarray.

💡 Sorted + 'find a set that satisfies a constraint' = two pointers.

Flashcard

In the opposite-ends technique for finding a pair with a target sum, how do you decide which pointer to move, and why is the move safe?

tap to reveal →

Start one pointer at the beginning and one at the end. If the current sum is greater than the target, decrement the end pointer to seek a smaller sum; if it is less than the target, increment the start pointer to seek a larger sum. Because the array is sorted, the discarded element can never form the pair, so skipping it is safe.

💡 Sum too big -> shrink from the right; too small -> grow from the left.

Flashcard

For Pair with Target Sum, what is the brute-force complexity versus the two-pointer complexity?

tap to reveal →

Brute force (taking one number at a time and binary-searching for the second) is O(N*logN). The two-pointer approach is O(N) time, finding the pair in a single inward pass; if no pair exists it returns [-1, -1].

💡 Binary-search brute force N*logN; two pointers collapse it to one O(N) sweep.

Flashcard

How does the Dutch National Flag algorithm sort an array of 0s, 1s, and 2s in place using three indices low, high, and i?

tap to reveal →

Iterate with i while i <= high. If arr[i]==0, swap with arr[low] and increment both low and i. If arr[i]==1, just increment i. If arr[i]==2, swap with arr[high] and decrement high WITHOUT moving i (the swapped-in value still needs checking). All 0s end up before low, all 2s after high, 1s in the middle.

💡 0 -> swap-low & advance both; 1 -> step over; 2 -> swap-high & stay put.

Flashcard

Comparing Strings with Backspaces: why scan from the end, and how are '#' characters handled?

tap to reveal →

Place a pointer at the last index of each string and move backward. A backspace count tracks pending '#'s: each '#' increments the count, and each real character either cancels a pending backspace (skipped) or, if no backspaces remain, becomes the next valid character to compare. Scanning from the end lets you resolve backspaces correctly with O(1) extra space instead of building the strings.

💡 Read backwards; '#' adds to a delete-debt, letters pay it off before counting.

Flashcard

In Minimum Window Sort, why isn't the window just between the first out-of-order element from each end, and how is it fixed?

tap to reveal →

First find the first out-of-order element from the left (smaller than its predecessor) and from the right (bigger than its successor). That window is not enough: you must find the subarray's min and max, then extend low left past any element greater than the subarray min, and extend high right past any element smaller than the subarray max. Answer length = high - low + 1; return 0 if already sorted. Time O(N), space O(1).

💡 Find rough window, then stretch it to swallow every element outside the subarray's min/max.

Q1. When is the Two Pointers pattern the natural fit, according to the lessons?

Q2. For Pair with Target Sum on input [1, 2, 3, 4, 6] with target 6, what does the function return?

Q3. In the opposite-ends approach for Pair with Target Sum, what do you do when the current sum is greater than the target?

Q4. In Dutch National Flag, when arr[i] equals 2 you swap arr[i] with arr[high]. What happens to i and high next?

Q5. For Minimum Window Sort on input [1, 3, 2, 0, -1, 7, 10], why is the answer 5 rather than the window between the first out-of-order elements (3 and -1)?