👆👆 Two Pointers Technique — Complete Guide
Index: Two Pointers Index | Parent: Array Index
What is the Two Pointers Technique?
Use two variables (pointers) that move through the array to solve problems in O(n) that would normally require O(n²) with nested loops.
When to use Two Pointers?
- Array is sorted (or can be sorted)
- You need to find a pair or triplet that satisfies a condition
- You need to compare elements from both ends
- You need to partition or rearrange elements
- Keywords: "pair sum", "duplicates", "reverse", "palindrome", "remove elements"
Pattern 1: Opposite Direction (Start & End)
Both pointers start at opposite ends and move toward each other.
L → ← R
[1, 2, 3, 4, 5, 6, 7]Template:
function twoPointersOpposite(array $arr): mixed {
$left = 0;
$right = count($arr) - 1;
while ($left < $right) {
// Check condition using $arr[$left] and $arr[$right]
if (/* condition met */) {
return /* result */;
} elseif (/* need larger sum/value */) {
$left++;
} else {
$right--;
}
}
return null; // not found
}Pattern 2: Same Direction (Fast & Slow)
Both pointers start at beginning. Fast moves ahead, slow follows.
S
F →
[1, 2, 2, 3, 3, 4, 5]Template:
function twoPointersSameDir(array $arr): array {
$slow = 0;
for ($fast = 1; $fast < count($arr); $fast++) {
if (/* condition */) {
$slow++;
$arr[$slow] = $arr[$fast];
}
}
return array_slice($arr, 0, $slow + 1);
}Interview Questions — Two Pointers
Q1. Two Sum — Find pair that equals target [E][FB]
Question: In sorted array [1,2,3,4,6], find pair summing to 6. Return indices.
🧠 How to Approach This
Step 1 — Recognize the pattern:
The array is sorted. You need a pair with a specific sum. These two signals together = Two Pointers opposite direction.
Step 2 — Brute force (what NOT to do):
Two nested loops check every pair → O(n²). With n=100,000 that's 10 billion operations.
Step 3 — Optimal insight:
Start with the smallest (left) and largest (right) values. Their sum tells you which direction to move:
- Sum too small → need a bigger number → move left pointer right
- Sum too large → need a smaller number → move right pointer left
- Sum matches → done!
Step 4 — Algorithm:
1. Set L=0, R=n-1
2. While L < R: compute sum
3. sum == target → return [L, R]
4. sum < target → L++ (get bigger left value)
5. sum > target → R-- (get smaller right value)
Step 5 — Edge cases:
- Array must be sorted for this to work
- No pair exists: return [] after loop ends
[1, 2, 3, 4, 6] target=6
L R sum=7 > 6 → R--
L R sum=5 < 6 → L++
L R sum=6 ✅ Found! (indices 1,3)function twoSum(array $arr, int $target): array {
$left = 0;
$right = count($arr) - 1;
while ($left < $right) {
$sum = $arr[$left] + $arr[$right];
if ($sum === $target) return [$left, $right];
elseif ($sum < $target) $left++;
else $right--;
}
return []; // not found
}
print_r(twoSum([1,2,3,4,6], 6)); // [1, 3] (values 2+4=6)Time: O(n) | Space: O(1)
JavaScript:
function twoSum(arr, target) {
let left = 0, right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) return [left, right];
sum < target ? left++ : right--;
}
return [];
}Q2. Three Sum — Find all triplets summing to 0 [M][FB]
Question: Find all unique triplets in [-1,0,1,2,-1,-4] that sum to 0.
🧠 How to Approach This
Step 1 — Recognize the pattern:
Two pointers on a sorted array, but for TRIPLETS instead of pairs.
Step 2 — Brute force (what NOT to do):
Three nested loops = O(n³). For n=1000 that's a billion iterations.
Step 3 — Optimal insight:
Fix one element with the outer loop. Now the problem reduces to finding a pair summing to
-arr[i]— which is a two-pointer problem! Sort first to enable skipping duplicates.Step 4 — Algorithm:
1. Sort the array
2. Outer loop: fix arr[i] (i = 0 to n-3)
3. Skip if arr[i] == arr[i-1] (duplicate i)
4. Two pointers: L=i+1, R=n-1; find pair summing to -arr[i]
5. On match: save triplet, skip duplicate L values, skip duplicate R values
Step 5 — Edge cases:
- [0,0,0] → valid triplet
- All positive: no triplets possible (everything > 0)
- Skip duplicates at ALL three levels (i, L, R)
function threeSum(array $arr): array {
sort($arr);
$result = [];
$n = count($arr);
for ($i = 0; $i < $n - 2; $i++) {
// Skip duplicates for first element
if ($i > 0 && $arr[$i] === $arr[$i - 1]) continue;
$left = $i + 1;
$right = $n - 1;
while ($left < $right) {
$sum = $arr[$i] + $arr[$left] + $arr[$right];
if ($sum === 0) {
$result[] = [$arr[$i], $arr[$left], $arr[$right]];
// Skip duplicates
while ($left < $right && $arr[$left] === $arr[$left + 1]) $left++;
while ($left < $right && $arr[$right] === $arr[$right - 1]) $right--;
$left++;
$right--;
} elseif ($sum < 0) {
$left++;
} else {
$right--;
}
}
}
return $result;
}
print_r(threeSum([-1,0,1,2,-1,-4]));
// [[-1,-1,2], [-1,0,1]]Time: O(n²) | Space: O(1) (not counting output)
Q3. Remove Duplicates from Sorted Array (in-place) [E][FB]
Question: Remove duplicates from [1,1,2,3,3,3,4] in-place. Return new length.
🧠 How to Approach This
Step 1 — Recognize the pattern:
In-place rearrangement of a sorted array = Slow/Fast pointer (same direction).
Step 2 — Brute force (what NOT to do):
Copy to new array, filter. Requires O(n) extra space. Interview wants O(1) space.
Step 3 — Optimal insight:
Slow pointer marks the "write position" — where the next unique value should go.
Fast pointer scans ahead. When it finds a value different from arr[slow], copy it to slow+1.
Step 4 — Algorithm:
1. slow = 0 (first unique position)
2. fast = 1 to n-1
3. If arr[fast] ≠ arr[slow]: slow++, arr[slow] = arr[fast]
4. Return slow+1 (count of unique elements)
Step 5 — Edge cases:
- Empty array: return 0
- All same: return 1
- No duplicates: slow follows fast exactly
[1, 1, 2, 3, 3, 3, 4]
S
F arr[F]=1 == arr[S]=1 → skip
F arr[F]=2 != arr[S]=1 → slow++, write 2
S F arr[F]=3 != arr[S]=2 → slow++, write 3
S F arr[F]=3 == arr[S]=3 → skip
F arr[F]=3 == arr[S]=3 → skip
F arr[F]=4 != arr[S]=3 → slow++, write 4
Result: [1,2,3,4,...] length=4function removeDuplicatesInPlace(array $arr): int {
if (empty($arr)) return 0;
$slow = 0;
for ($fast = 1; $fast < count($arr); $fast++) {
if ($arr[$fast] !== $arr[$slow]) {
$slow++;
$arr[$slow] = $arr[$fast];
}
}
return $slow + 1; // new length
}
echo removeDuplicatesInPlace([1,1,2,3,3,3,4]); // 4Q4. Container With Most Water [M][FB]
Question: Given heights [1,8,6,2,5,4,8,3,7], find two lines that form container with most water.
🧠 How to Approach This
Step 1 — Recognize the pattern:
Maximizing area between two elements → Two pointers (opposite direction).
Step 2 — Brute force (what NOT to do):
Check every pair of walls: O(n²).
Step 3 — Optimal insight:
Area = min(height[L], height[R]) × (R - L).
As we move pointers inward, width decreases. Our only hope of increasing area is to find a TALLER wall. So: always move the pointer with the SHORTER wall. Moving the taller wall can never improve area (width shrinks, height is still limited by the shorter side).
Step 4 — Algorithm:
1. L=0, R=n-1, maxArea=0
2. Compute area = min(heights[L], heights[R]) × (R-L)
3. Update maxArea
4. Move the shorter pointer inward (if equal, move either)
Step 5 — Edge cases:
- All same heights: area shrinks with every step, max is at outermost pair
- Two elements: only one calculation needed
function maxWater(array $heights): int {
$left = 0;
$right = count($heights) - 1;
$maxArea = 0;
while ($left < $right) {
$area = min($heights[$left], $heights[$right]) * ($right - $left);
$maxArea = max($maxArea, $area);
if ($heights[$left] < $heights[$right]) {
$left++; // move shorter side
} else {
$right--;
}
}
return $maxArea;
}
echo maxWater([1,8,6,2,5,4,8,3,7]); // 49Time: O(n) | Space: O(1)
Q5. Valid Palindrome [E][FB]
Question: Is "A man, a plan, a canal: Panama" a palindrome (ignoring non-alphanumeric)?
🧠 How to Approach This
Step 1 — Recognize the pattern:
Checking both ends of a sequence = Two Pointers (opposite direction).
Step 2 — Key insight:
Process only alphanumeric characters. Compare lowercase versions of chars at L and R.
Skip non-alphanumeric chars by advancing the relevant pointer.
Step 3 — Algorithm:
1. L=0, R=strlen(s)-1
2. While L < R: skip non-alphanumeric on both sides
3. If lowercase s[L] ≠ lowercase s[R] → false
4. Advance both L++ R--
5. Return true
Step 4 — Edge cases:
- Empty string → true (palindrome by definition)
- All non-alphanumeric → true (empty after filtering)
- Single character → true
function isPalindrome(string $s): bool {
$left = 0;
$right = strlen($s) - 1;
while ($left < $right) {
// Skip non-alphanumeric from left
while ($left < $right && !ctype_alnum($s[$left])) $left++;
// Skip non-alphanumeric from right
while ($left < $right && !ctype_alnum($s[$right])) $right--;
if (strtolower($s[$left]) !== strtolower($s[$right])) return false;
$left++;
$right--;
}
return true;
}
var_dump(isPalindrome("A man, a plan, a canal: Panama")); // true
var_dump(isPalindrome("race a car")); // falsefunction isPalindrome(s) {
s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) return false;
left++; right--;
}
return true;
}Q6. Trap Rainwater [H][FB]
Question: Given [0,1,0,2,1,0,1,3,2,1,2,1], how much water is trapped?
🧠 How to Approach This
Step 1 — Recognize the pattern:
Each position traps water equal to min(maxLeft, maxRight) - height[i]. Two Pointers lets us compute this in O(1) space.
Step 2 — Brute force (what NOT to do):
For each index, scan left for maxLeft and scan right for maxRight → O(n²).
Step 3 — Pre-computed arrays (better):
Pre-compute leftMax[] and rightMax[] arrays, then a single pass for water. O(n) time, O(n) space.
Step 4 — Two Pointer insight (best — O(1) space):
The water at position i is bounded by min(maxLeft, maxRight). If height[L] < height[R], then we KNOW the left side's bound is maxLeft (right side is at least height[R] which is bigger). Process the left side with confidence.
Step 5 — Algorithm:
1. L=0, R=n-1, maxLeft=0, maxRight=0, water=0
2. While L < R:
- If heights[L] <= heights[R]: process left side
- heights[L] >= maxLeft? → new maxLeft (no water here)
- else → water += maxLeft - heights[L]
- Else: process right side symmetrically
Step 6 — Edge cases:
- Monotonically increasing/decreasing → no water trapped
[0,1,0,2,1,0,1,3,2,1,2,1]
↑ ↑
water water
Total = 6function trapRainwater(array $heights): int {
$left = 0;
$right = count($heights) - 1;
$maxLeft = 0;
$maxRight = 0;
$water = 0;
while ($left < $right) {
if ($heights[$left] <= $heights[$right]) {
if ($heights[$left] >= $maxLeft) {
$maxLeft = $heights[$left]; // update max, no water here
} else {
$water += $maxLeft - $heights[$left]; // trapped water
}
$left++;
} else {
if ($heights[$right] >= $maxRight) {
$maxRight = $heights[$right];
} else {
$water += $maxRight - $heights[$right];
}
$right--;
}
}
return $water;
}
echo trapRainwater([0,1,0,2,1,0,1,3,2,1,2,1]); // 6Time: O(n) | Space: O(1)
Q7. Move Zeros to End [E][FB][L]
Question: Move all zeros to end while maintaining order of non-zeros.
[0,1,0,3,12] → [1,3,12,0,0]🧠 How to Approach This
Step 1 — Recognize the pattern:
In-place rearrangement maintaining relative order = Slow/Fast pointers (same direction).
Step 2 — Key insight:
Slow pointer tracks the "write position" for non-zeros. Fast scans for non-zero values and writes them to slow position. After the loop, fill remaining positions with zeros.
Step 3 — Algorithm:
1. slow = 0; for fast in 0..n-1: if arr[fast] ≠ 0 → arr[slow] = arr[fast], slow++
2. Fill arr[slow..n-1] with zeros
Step 4 — Edge cases:
- All zeros: slow stays at 0, fill entire array with zeros
- No zeros: slow and fast march together, no changes needed
function moveZeros(array $arr): array {
$slow = 0;
// Move non-zeros to front
for ($fast = 0; $fast < count($arr); $fast++) {
if ($arr[$fast] !== 0) {
$arr[$slow] = $arr[$fast];
$slow++;
}
}
// Fill rest with zeros
while ($slow < count($arr)) {
$arr[$slow++] = 0;
}
return $arr;
}
print_r(moveZeros([0,1,0,3,12])); // [1,3,12,0,0]Q8. Sort Array by Parity [E]
Question: Move even numbers to front, odd to back. In-place.
🧠 How to Approach This
Step 1 — Recognize the pattern:
Partitioning array into two groups = Two Pointers (opposite direction), similar to Dutch National Flag.
Step 2 — Key insight:
Left pointer looks for the first ODD (misplaced on left side). Right pointer looks for the first EVEN (misplaced on right side). Swap them. Repeat.
Step 3 — Algorithm:
1. L=0, R=n-1
2. Advance L while arr[L] is even (already in place)
3. Advance R while arr[R] is odd (already in place)
4. If L < R: swap arr[L] and arr[R], L++, R--
Step 4 — Edge cases:
- All even: L walks all the way to end, no swaps needed
- All odd: R walks all the way to start, no swaps needed
function sortByParity(array $arr): array { $left = 0; $right = count($arr) - 1;
while ($left < $right) { while ($left < $right && $arr[$left] % 2 === 0) $left++; // even, skip while ($left < $right && $arr[$right] % 2 !== 0) $right--; // odd, skip if ($left < $right) { [$arr[$left], $arr[$right]] = [$arr[$right], $arr[$left]]; $left++; $right--; } } return $arr; }
print_r(sortByParity([3,1,2,4])); // [4,2,1,3] or [2,4,3,1]
---
## Two Pointers Pattern Summary
| Problem Pattern | Pointer Setup | Movement Rule |
|----------------|--------------|---------------|
| Pair sum in sorted | L=0, R=end | sum<target: L++; sum>target: R-- |
| Palindrome check | L=0, R=end | mismatch: return false; both move in |
| Remove duplicates | slow=0, fast=1 | fast!=slow: slow++, write |
| Partition (even/odd) | L=0, R=end | swap when wrong side |
| Move zeros | slow=0, fast=0 | non-zero: write to slow, slow++ |
| Merge sorted arrays | i=0, j=0 | pick smaller, advance that pointer |
| Container with water | L=0, R=end | move shorter side inward |
| Trap rainwater | L=0, R=end | process smaller side |