Chapter 06 — Two Pointers
Chapter 06 — Two Pointers
Hey everyone! Welcome to Season 2 — Patterns!
This season is where DSA gets fun, because we learn the patterns interviewers actually test. First up: Two Pointers. The idea is simple — instead of one index crawling through the array, you use two indices moving cleverly. This often collapses an O(n²) brute force into a clean O(n).
What we will cover:
- The two-pointer idea (opposite ends & same direction)
- Pair sum in a sorted array
- Reverse in place
- Remove duplicates in O(1) space
- Fast & slow pointers (cycle detection preview)
- When two pointers beats a nested loop
- Interview Questions
1. The Two-Pointer Idea
┌─────────────────────────────────────────────────────────────┐ │ TWO FLAVORS OF TWO POINTERS │ ├─────────────────────────────────────────────────────────────┤ │ │ │ A) OPPOSITE ENDS — start + end, move toward middle │ │ [ ● . . . . . ● ] │ │ L → ← R │ │ Used for: sorted pair-sum, palindrome, reverse │ │ │ │ B) SAME DIRECTION — slow + fast, both move forward │ │ [ ● ● . . . . . ] │ │ slow fast → │ │ Used for: dedupe, remove element, cycle detection │ │ │ └─────────────────────────────────────────────────────────────┘
2. Pair Sum in a Sorted Array
Given a sorted array, find two numbers that add to a target. Brute force is O(n²). With two pointers it's O(n) — and O(1) space.
function pairSum(arr, target) {
let l = 0, r = arr.length - 1;
while (l < r) {
const sum = arr[l] + arr[r];
if (sum === target) return [l, r];
if (sum < target) l++; // need bigger → move left up
else r--; // need smaller → move right down
}
return [];
}
HAND TRACE: pairSum([1, 3, 4, 6, 8], 10) l=0(1) r=4(8) → sum=9 < 10 → l++ l=1(3) r=4(8) → sum=11 > 10 → r-- l=1(3) r=3(6) → sum=9 < 10 → l++ l=2(4) r=3(6) → sum=10 == 10 → return [2, 3] ✔
Why it works: sorting means moving l right only increases the sum, and moving r left only decreases it. So each step makes a guaranteed correct decision — no need to check every pair.
3. Reverse In Place
function reverse(arr) {
let l = 0, r = arr.length - 1;
while (l < r) {
[arr[l], arr[r]] = [arr[r], arr[l]];
l++; r--;
}
return arr;
}
// O(n) time, O(1) space
4. Remove Duplicates from a Sorted Array (O(1) space)
Use a slow pointer marking where the next unique value goes, and a fast pointer scanning ahead.
function removeDuplicates(arr) {
if (arr.length === 0) return 0;
let slow = 0;
for (let fast = 1; fast < arr.length; fast++) {
if (arr[fast] !== arr[slow]) {
slow++;
arr[slow] = arr[fast]; // place next unique
}
}
return slow + 1; // length of unique part
}
HAND TRACE: [1, 1, 2, 3, 3] slow=0 fast=1: arr[1]=1 == arr[0]=1 → skip fast=2: arr[2]=2 != 1 → slow=1, arr[1]=2 → [1,2,2,3,3] fast=3: arr[3]=3 != 2 → slow=2, arr[2]=3 → [1,2,3,3,3] fast=4: arr[4]=3 == 3 → skip return slow+1 = 3 → unique part [1,2,3] ✔
5. Fast & Slow Pointers (Floyd's Cycle Detection)
Move one pointer 1 step and another 2 steps. If there's a loop, the fast one eventually "laps" and meets the slow one. We'll use this heavily for linked lists (Chapter 08).
┌─────────────────────────────────────────────────────────────┐ │ slow moves 1 step, fast moves 2 steps │ │ If they ever meet → there is a CYCLE │ │ If fast reaches the end (null) → NO cycle │ └─────────────────────────────────────────────────────────────┘
6. When Two Pointers Beats a Nested Loop
USE TWO POINTERS WHEN: ✔ The array is SORTED (or you can sort it) ✔ You're looking for a PAIR / TRIPLET with a condition ✔ You need to do something IN PLACE (O(1) space) ✔ You can make a correct move based on a comparison Result: O(n²) brute force → O(n) (or O(n log n) if you sort first)
Interview Questions — Quick Fire!
Q: What is the two-pointer technique?
"Using two indices that move through the data in a coordinated way — either from opposite ends toward the middle, or both forward at different speeds. It often reduces an O(n²) brute force to O(n) with O(1) extra space."
Q: Why does the sorted pair-sum two-pointer approach work?
"Because the array is sorted, moving the left pointer right always increases the sum and moving the right pointer left always decreases it. So comparing the current sum to the target tells you exactly which pointer to move — no need to test every pair."
Q: How do you remove duplicates from a sorted array in O(1) space?
"Use a slow pointer marking the position for the next unique value and a fast pointer scanning ahead. Whenever the fast value differs from the slow value, advance slow and copy the new value there. It's O(n) time and modifies the array in place."
Q: What are fast and slow pointers used for?
"Mainly cycle detection and finding the middle of a linked list. Moving one pointer twice as fast as the other means if there's a loop they'll eventually meet, and when the fast one reaches the end the slow one is at the middle."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| Opposite ends | L & R move inward — sorted pair-sum, palindrome. |
| Same direction | slow & fast — dedupe, cycle detection. |
| Sorted pair sum | O(n), O(1) space. |
| In-place dedupe | slow marks unique spot. |
| When to use | Sorted data, pairs, in-place, O(n²)→O(n). |
What's Next?
Chapter 07: Sliding Window — the sibling of two pointers, perfect for "best subarray/substring of size k" problems. You'll never write a triple-nested loop for substrings again.
Keep coding, keep grinding! See you in the next one!
Post a Comment