What the technique is
Many array problems ask about a contiguous stretch of elements: a pair, a run, a window. Checking every stretch with nested loops costs O(n²) or worse. The two pointers technique replaces the inner loop with a second index that only moves in one direction. Because neither index ever goes back, the whole scan is O(n).
There are two common shapes:
- Pointers from both ends. One index starts at the left end, one at the right end, and they move toward each other. It suits sorted arrays and symmetric checks.
- A sliding window. Both indices start on the left. The right one grows the window and the left one shrinks it, so the window slides over the array. It suits problems about the longest or shortest contiguous run that satisfies a condition.
Pointers from both ends
Take a sorted slice and a target, and look for two elements that add up to it. Compare the sum of the two ends with the target. If it is too small, the left element is too small to work with anything that remains, so move left right. If it is too big, move right left. Each step discards one element for good.
fn pair_with_sum(sorted: &[i32], target: i32) -> Option<(usize, usize)> {
if sorted.is_empty() {
return None;
}
let mut left = 0;
let mut right = sorted.len() - 1;
while left < right {
let sum = sorted[left] + sorted[right];
if sum == target {
return Some((left, right));
} else if sum < target {
left += 1;
} else {
right -= 1;
}
}
None
}
For [1, 3, 4, 6, 8, 11] and target 10 the function returns Some((2, 3)), the elements 4 and 6. For [1, 3, 4] and target 100 it returns None.
A fixed-size sliding window
When the window always has k elements, slide it by adding the element that enters and subtracting the one that leaves. Each slide is constant work, instead of re-adding k elements.
fn max_sum_of_k(nums: &[i32], k: usize) -> i32 {
let mut window: i32 = nums[..k].iter().sum();
let mut best = window;
for i in k..nums.len() {
window += nums[i] - nums[i - k];
best = best.max(window);
}
best
}
For [2, 1, 5, 1, 3, 2] and k = 3 this returns 9, from the window [5, 1, 3].
A window that grows and shrinks
For "the longest run whose sum is at most s", with positive numbers, the size is not fixed. Move right one step at a time and add the new element. While the sum is over the limit, remove elements from the left until it fits again. After each step the window is valid, so its length is a candidate.
fn longest_at_most(nums: &[i32], s: i32) -> usize {
let mut best = 0;
let mut sum = 0;
let mut left = 0;
for right in 0..nums.len() {
sum += nums[right];
while sum > s {
sum -= nums[left];
left += 1;
}
best = best.max(right + 1 - left);
}
best
}
On [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] with s = 11 it returns 6. On [9, 1, 1] with s = 3 it returns 2: the 9 is added, then removed at once, and the window moves on.
Why is this linear? Each index only moves forward. right advances n times and left advances at most n times in total, even though the while sits inside the for. The inner loop does not restart; it continues from where left stopped.
The technique relies on positive numbers. With negative values, removing an element can make the sum bigger, and the shrink-until-valid idea no longer works.
Rust details that matter here
- Indices are
usize. Vectors and slices are indexed only withusize, and sums are usuallyi32. Mixing them needs an explicit cast withas, for example when a function returns indices asi32. usizecannot go below zero.sorted.len() - 1on an empty slice underflows. In a debug build that panics; in an optimized build it wraps to a huge number. That is whypair_with_sumchecks for an empty slice first. Movingrightleft is safe inside the loop, becauserightis greater thanleftthere, so it is at least 1.- Slices borrow.
&[i32]is a view of the elements, so a function can take&vecor&arraywithout copying. A sub-range such as&nums[1..4]is a view too, andnums[..k].iter().sum()adds up the firstkelements. windows(k). The standard library has a method that yields every fixed-size window.[1, 2, 3, 4, 5].windows(3)gives[1, 2, 3],[2, 3, 4]and[3, 4, 5]. It is convenient for fixed windows, but it cannot grow or shrink, so variable windows need two indices.- Short-circuit conditions. In a loop condition such as
last < n && sum + nums[last] <= s, the&&stops as soon as the first part is false, so the indexing on the right never runs out of bounds. - Out-of-bounds indexing panics. Rust never reads past the end; it stops the program with a panic. Guard every index that moves.
How to approach a new problem
- Ask whether the answer is a contiguous stretch, or a pair in sorted data.
- Decide what each pointer means and the only directions it may move.
- Decide what the loop keeps true after every step, for example "the window sum is at most
s". - Write what happens when a pointer moves: what is added, what is removed, and when the best answer is updated.
- Check the empty input, a single element, and the case where nothing qualifies.
Key takeaways
- Two pointers turn nested loops into one scan, because the pointers never move backward.
- Pointers from both ends fit sorted data; a sliding window fits contiguous runs.
- A window can be fixed in size or can grow and shrink, but each element enters and leaves at most once, so the time stays
O(n). - In Rust, watch the
usizeindices: casts toi32must be explicit, and subtracting from zero underflows.
