Two Pointers
Maintain two indices moving toward each other or in the same direction to solve problems that would otherwise require nested loops. The most versatile O(n) array technique.
The Pattern
Two pointers is a technique where two indices move through a data structure, either toward each other from opposite ends (the collision variant) or in the same direction at different speeds (the fast/slow variant). The key insight is that for sorted data or problems with a monotone property, you can eliminate the inner loop of an O(n²) brute force by making a guaranteed decision about which pointer to move.
The collision variant starts with left at index 0 and right at the last index. At each step, the current state tells you definitively which pointer to advance — making progress without backtracking and visiting each element at most once.
Two Sum in a Sorted Array
Given a sorted array and a target, find indices of two elements that sum to the target. Brute force is O(n²). With sorted data, if the sum of arr[left] + arr[right] is too small, the only way to increase it is to advance left. If too large, retreat right. The pointers converge in O(n).
fn two_sum_sorted(arr: &[i32], target: i32) -> Option<(usize, usize)> {
let (mut l, mut r) = (0, arr.len().saturating_sub(1));
while l < r {
match (arr[l] + arr[r]).cmp(&target) {
std::cmp::Ordering::Equal => return Some((l, r)),
std::cmp::Ordering::Less => l += 1,
std::cmp::Ordering::Greater => r -= 1,
}
}
None
}
fn main() {
let arr = [1, 2, 4, 6, 8, 10];
println!("{:?}", two_sum_sorted(&arr, 10)); // Some((1, 4)) → 2 + 8
println!("{:?}", two_sum_sorted(&arr, 3)); // Some((0, 1)) → 1 + 2
}Three Sum — All Unique Triplets
Find all unique triplets in an unsorted array that sum to zero. Sort the array first. Fix one element and run two pointers on the remaining subarray. Skip duplicates after each match and whenever the pointer lands on the same value as its previous position.
fn three_sum(mut nums: Vec<i32>) -> Vec<[i32; 3]> {
nums.sort_unstable();
let n = nums.len();
let mut result = Vec::new();
for i in 0..n.saturating_sub(2) {
if i > 0 && nums[i] == nums[i - 1] { continue; } // skip duplicate fixed element
let (mut l, mut r) = (i + 1, n - 1);
while l < r {
let s = nums[i] + nums[l] + nums[r];
match s.cmp(&0) {
std::cmp::Ordering::Equal => {
result.push([nums[i], nums[l], nums[r]]);
while l < r && nums[l] == nums[l + 1] { l += 1; }
while l < r && nums[r] == nums[r - 1] { r -= 1; }
l += 1; r -= 1;
}
std::cmp::Ordering::Less => l += 1,
std::cmp::Ordering::Greater => r -= 1,
}
}
}
result
}
fn main() {
let nums = vec![-1, 0, 1, 2, -1, -4];
println!("{:?}", three_sum(nums)); // [[-1,-1,2], [-1,0,1]]
}Container with Most Water
Given heights of vertical bars, find two bars that together with the x-axis form a container holding the most water. The area is min(height[l], height[r]) * (r - l). Start with the widest container (l=0, r=n-1). Closing the width can only help if we find a taller bar — so always move the pointer at the shorter bar inward.
fn max_area(heights: &[i32]) -> i32 {
let (mut l, mut r) = (0, heights.len() - 1);
let mut best = 0;
while l < r {
let area = heights[l].min(heights[r]) * (r - l) as i32;
best = best.max(area);
if heights[l] < heights[r] { l += 1; } else { r -= 1; }
}
best
}
fn main() {
println!("{}", max_area(&[1,8,6,2,5,4,8,3,7])); // 49
println!("{}", max_area(&[1,1])); // 1
}Trapping Rain Water
Given bar heights, compute how much water can be trapped after rain. Each position can hold water equal to min(max_left, max_right) - height[i]. Instead of precomputing prefix/suffix maxima, use two pointers: maintain running left_max and right_max. The pointer on the side with the smaller running max can be resolved immediately — it is guaranteed that the other side has a wall at least as tall.
fn trap(heights: &[i32]) -> i32 {
let (mut l, mut r) = (0, heights.len() - 1);
let (mut left_max, mut right_max) = (0, 0);
let mut water = 0;
while l < r {
if heights[l] < heights[r] {
left_max = left_max.max(heights[l]);
water += left_max - heights[l];
l += 1;
} else {
right_max = right_max.max(heights[r]);
water += right_max - heights[r];
r -= 1;
}
}
water
}
fn main() {
println!("{}", trap(&[0,1,0,2,1,0,1,3,2,1,2,1])); // 6
println!("{}", trap(&[4,2,0,3,2,5])); // 9
}Remove Duplicates from Sorted Array — In-Place
Keep only unique elements in a sorted array, returning the new length. Use a slow pointer that tracks the last unique element written, and a fast pointer that scans ahead.
fn remove_duplicates(nums: &mut Vec<i32>) -> usize {
if nums.is_empty() { return 0; }
let mut slow = 0;
for fast in 1..nums.len() {
if nums[fast] != nums[slow] {
slow += 1;
nums[slow] = nums[fast];
}
}
slow + 1
}
fn main() {
let mut nums = vec![0,0,1,1,1,2,2,3,3,4];
let k = remove_duplicates(&mut nums);
println!("{}: {:?}", k, &nums[..k]); // 5: [0, 1, 2, 3, 4]
}Valid Palindrome
A string is a palindrome if it reads the same forwards and backwards, ignoring non-alphanumeric characters and case. Two pointers advance from both ends, skipping non-alphanumeric characters, and compare the remaining characters.
fn is_palindrome(s: &str) -> bool {
let chars: Vec<char> = s.chars()
.filter(|c| c.is_alphanumeric())
.map(|c| c.to_ascii_lowercase())
.collect();
let (mut l, mut r) = (0, chars.len().saturating_sub(1));
while l < r {
if chars[l] != chars[r] { return false; }
l += 1; r -= 1;
}
true
}
fn main() {
println!("{}", is_palindrome("A man, a plan, a canal: Panama")); // true
println!("{}", is_palindrome("race a car")); // false
}Sort Colors / Move Zeros — Three Pointers
Move all zeros to the end while maintaining the relative order of non-zero elements. A write pointer tracks where the next non-zero element should go; a read pointer scans ahead. After processing, fill the remainder with zeros.
fn move_zeros(nums: &mut Vec<i32>) {
let mut write = 0;
for read in 0..nums.len() {
if nums[read] != 0 {
nums[write] = nums[read];
write += 1;
}
}
for i in write..nums.len() { nums[i] = 0; }
}
fn main() {
let mut nums = vec![0, 1, 0, 3, 12];
move_zeros(&mut nums);
println!("{:?}", nums); // [1, 3, 12, 0, 0]
}