👈👉 Two Pointers
One-line summary: Use two indices that move toward each other (or in the same direction) to eliminate the O(n²) nested loop — achieving O(n) on sorted data.
Concept
Two pointers maintains two indices — left and right — and moves them strategically:
- Opposite-direction (converging): both ends converge inward — sorted array, palindrome, container problems.
- Same-direction (fast/slow): both move forward, one faster — remove duplicates, cycle detection, is-subsequence.
Prerequisite: sorted array (for opposite-direction), or logical ordering for same-direction.
Diagram
Sorted: [1, 2, 3, 4, 6] target=6
L R
Step 1: 1+6=7 > 6 → R--
Step 2: 1+4=5 < 6 → L++
Step 3: 2+4=6 ✓
Time & Space Complexity
| Variant | Time | Space |
|---|---|---|
| Two Sum Sorted | O(n) | O(1) |
| Remove duplicates / Move Zeroes | O(n) | O(1) |
| Merge sorted arrays | O(m+n) | O(1) |
| Is Subsequence | O(n) | O(1) |
| Trapping Rain Water | O(n) | O(1) |
Common Patterns
Pattern 1 — Opposite Direction (Two Sum Sorted)
function twoSumSorted(arr, target) {
let left = 0, right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) return [left, right];
if (sum < target) left++;
else right--;
}
return [];
}
Pattern 2 — Same Direction (Move Zeroes)
function moveZeroes(nums) {
let insertPos = 0;
for (let i = 0; i < nums.length; i++)
if (nums[i] !== 0) nums[insertPos++] = nums[i];
while (insertPos < nums.length) nums[insertPos++] = 0;
}
Pattern 3 — Fast/Slow (Is Subsequence)
function isSubsequence(s, t) {
let i = 0, j = 0;
while (i < s.length && j < t.length) {
if (s[i] === t[j]) i++;
j++;
}
return i === s.length;
}
Pattern 4 — Fast/Slow (Cycle Detection in Linked List)
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next; fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
When to Use
- Sorted arrays where you need to find pairs or triplets
- Problems requiring partitioning or rearranging elements
- Optimising brute-force O(n²) solutions to O(n)
- Palindrome checking in arrays/strings
- Cycle detection in linked lists (fast/slow variant)
Pitfalls
- Forgetting to sort the array first (opposite-direction only works on sorted input)
- Moving both pointers simultaneously instead of one at a time
- Off-by-one: use
left < rightnotleft <= rightfor converging pointers
Practice Problems
Related Topics
- Sliding Window — same-direction two pointers with a window constraint
- Binary Search — both reduce search space
- Sorting — prerequisite for opposite-direction
- Linked List — fast/slow pointer variant
← Back to Home · © sparshjaswal