Algorithms from zero
Two pointers
You have an array and a problem that feels like it needs two nested loops—maybe you are comparing every pair of elements. Then someone shows you a different way: use two pointers instead of one, start them at opposite ends, and walk them toward the middle. The nested loop vanishes. A single pass through the array replaces it. This is the two-pointer technique.
After this lesson you can recognize when two pointers apply, code the two main shapes (opposite-ends and same-direction), understand why they turn O(n²) into O(n), and solve classic problems: checking palindromes, two-sum on a sorted array, and removing duplicates in place.
The two-pointer technique uses two indices into the array instead of one. The power comes from moving the pointers under a rule: if a condition is true, move one pointer; if false, move the other. This rule does the work of a nested loop in a single pass.
Two main shapes:
1. Opposite-ends pattern
Start one pointer at the beginning (left = 0) and one at the end (right = arr.length - 1). Move them toward each other:
let left = 0, right = arr.length - 1;
while (left < right) {
// Process arr[left] and arr[right]
// Move left or right based on a condition
if (condition) {
left++;
} else {
right--;
}
}Common use: check if something is a palindrome (do the endpoints match?), or find a pair with a target sum (if the pair is too small, move left pointer right; if too large, move right pointer left).
2. Same-direction pattern (fast and slow)
Start both pointers at the beginning. One pointer (slow) advances carefully; the other (fast) runs ahead:
let slow = 0, fast = 0;
while (fast < arr.length) {
// Move fast pointer
fast++;
// Conditionally move slow pointer
if (condition) {
slow++;
}
}Common use: remove duplicates from a sorted array in place (slow marks the end of the unique elements; fast scans ahead and copies new unique values back to slow’s position).
Why it works:
A naive nested loop checks every pair: for each i, check all j where j > i. That is O(n²).
The two-pointer trick works because of an invariant: the rule that governs pointer movement guarantees that you never need to revisit a combination. For opposite-ends, as left moves right and right moves left, the gap shrinks; you visit each position exactly once. For same-direction, fast scouts ahead and hands discoveries to slow, which records them; again, one pass, no backtracking.
Important precondition for opposite-ends two-sum:
If you are finding two elements that sum to a target using opposite-ends, the array must be sorted. Without sorting, the rule “move left if sum is too small” does not guarantee you will find all pairs. Opposite-ends two-sum only works on sorted data.
Let us code three classic two-pointer problems:
1. Check if a string is a palindrome (opposite-ends):
function isPalindrome(s) {
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) {
return false; // Mismatch: not a palindrome
}
left++;
right--;
}
return true; // All pairs matched
}2. Two-sum on a sorted array (opposite-ends):
function twoSum(arr, target) {
// PRECONDITION: arr must be sorted
let left = 0, right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) {
return [left, right]; // Found the pair
} else if (sum < target) {
left++; // Sum too small, move left pointer right
} else {
right--; // Sum too large, move right pointer left
}
}
return null; // No pair found
}3. Remove duplicates from sorted array in place (same-direction):
function removeDuplicates(arr) {
// PRECONDITION: arr is sorted
let slow = 0;
for (let fast = 1; fast < arr.length; fast++) {
if (arr[fast] !== arr[slow]) {
slow++;
arr[slow] = arr[fast]; // Copy unique element to slow's position
}
}
return slow + 1; // Length of unique elements
}Try running these:
Let us trace the opposite-ends two-sum on [1, 3, 5, 7, 9] looking for target 12:
1
function twoSum(arr, target) {
2
let left = 0, right = arr.length - 1;
3
while (left < right) {
4
const sum = arr[left] + arr[right];
5
if (sum === target) return [left, right];
6
else if (sum < target) left++;
7
else right--;
8
}
9
return null;
10
}
Now trace same-direction remove duplicates on [1, 1, 2, 2, 3]:
1
function removeDuplicates(arr) {
2
let slow = 0;
3
for (let fast = 1; fast < arr.length; fast++) {
4
if (arr[fast] !== arr[slow]) {
5
slow++;
6
arr[slow] = arr[fast];
7
}
8
}
9
return slow + 1;
10
}
Both shapes visit each array element a bounded number of times:
| Problem | Time | Space | Notes |
|---|---|---|---|
| Palindrome check (opposite-ends) | O(n) | O(1) | One pass, two pointers |
| Two-sum sorted array (opposite-ends) | O(n) | O(1) | Requires array to be sorted |
| Remove duplicates in place (same-direction) | O(n) | O(1) | Modifies array, returns new length |
| Reverse array in place (opposite-ends) | O(n) | O(1) | Swap endpoints, move inward |
Why O(n) and not O(n²)?
A naive check of every pair is O(n²): for each left, check all right.
Two pointers: left and right together visit every position exactly once as they converge (opposite-ends) or as fast scouts and slow records (same-direction). No nested loop, one pass through the array.
Why does the opposite-ends two-sum algorithm require the array to be sorted?
In the same-direction (fast/slow) remove-duplicates algorithm, why does fast run ahead while slow marks unique positions?
Check if '[1, 2, 3, 2, 1]' is a palindrome. What will isPalindrome return? (1 = true, 0 = false)
After calling removeDuplicates on [5, 5, 5, 7, 7], how many unique elements are there?
In the opposite-ends pattern, when left and right meet (left >= right), what does it mean?
Common mistake
Applying opposite-ends two-sum to an unsorted array. If the array is [3, 1, 4, 2, 5] and you search for sum 6 using opposite-ends, you start at 3 and 5 (sum 8, too large). You move right pointer left to 2. Now 3 + 2 = 5 (too small). You move left to 1. Now 1 + 2 = 3 (still too small). You move left to 4. Now 4 + 2 = 6 (found!). This worked, but only by luck. The rule “move left if too small” does not guarantee correctness without sorting. The algorithm is unsound on unsorted data.
Edge cases
Empty or single-element arrays. If the array has 0 or 1 elements, the opposite-ends loop while (left < right) never enters (since 0 < 0 is false, or 0 < 1 is true only once but then left++, right— immediately exit). For same-direction, the loop for (let fast = 1; ...) starts fast at 1; if the array has only 1 element (index 0), fast = 1 is out of bounds and the loop never runs. Both patterns handle empty/single arrays correctly: they return true (palindrome) or the input unchanged.
Why does the two-pointer technique reduce an O(n²) nested-loop problem to O(n)?
The two-pointer technique uses two indices and a rule to solve problems in a single pass instead of nested loops.
Key facts:
-
Opposite-ends shape: Start at both ends, move toward the middle. Apply when checking symmetry (palindrome) or finding pairs in a sorted array.
-
Same-direction shape: Both start at the beginning; one scouts ahead, the other records. Apply when modifying an array in place or when a slow/fast rhythm is natural.
-
Why O(n), not O(n²)? The pointer movement rule ensures each position is visited at most once per pointer, not once per outer loop. No nested iteration.
-
Opposite-ends two-sum requires sorted input. Without sorting, the rule “move left if sum too small” is unsound.
-
Same-direction enables in-place modification. Fast finds; slow writes back, overwriting duplicates or stale values.
Next, you will see two pointers applied to linked lists (where traversal is the only way forward) and sliding windows (where two pointers track a range of elements under a different rule).