Two Pointers Visualization for Coding Interviews
Pair-sum, dedupe, reverse — the classic two-pointer pattern, animated.
Concept
Two Pointers is the first pattern to reach for whenever the input is a sorted array, a linked list where you need a slow/fast split, or any scan where a nested O(n^2) loop is really collapsing into two coordinated linear walks. The idea is simple: instead of re-scanning the suffix for every prefix index, keep two cursors that only ever move forward (or one from each end moving inward) and let the sorted order prune the search space. That collapses a brute O(n^2) into O(n) without extra memory, which is why it shows up in 3Sum, container-with-most-water, dedupe-in-place, partitioning, cycle detection, palindrome checks, and merging sorted streams. If you see the words 'sorted', 'pair', 'in-place', or 'without extra space', test a two-pointer sweep first.
How it works
There are two flavors. The opposed flavor seeds a left pointer at 0 and a right pointer at n-1, evaluates the pair (a[left], a[right]) against a target, and then advances exactly one pointer based on which direction would bring the pair closer to the target. Because the array is sorted, moving left forward monotonically increases the sum and moving right backward monotonically decreases it, so you never have to revisit a pair. The same-direction flavor uses a slow write-pointer and a fast read-pointer: fast scans every element, slow only advances when the invariant says 'keep this one'. Dedupe-sorted-in-place is the canonical example; slow ends up pointing one past the last kept element. The loop terminates when left >= right (opposed) or fast == n (same-direction). To avoid O(n^2) regressions, every iteration must move at least one pointer unconditionally, and duplicates must be skipped by advancing past equal neighbors inside the same pass, not by re-entering the outer loop. The pattern also composes: 3Sum fixes the first index with an outer loop and runs an opposed two-pointer sweep on the suffix, turning a naive O(n^3) into O(n^2) with O(1) extra memory beyond the sort.
Implementation
package dsa.twopointers;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public final class TwoPointers {
// Two-sum on a sorted array: returns 1-indexed pair or {-1,-1}.
public static int[] twoSumSorted(int[] a, int target) {
int l = 0, r = a.length - 1;
while (l < r) {
int sum = a[l] + a[r];
if (sum == target) return new int[]{l + 1, r + 1};
if (sum < target) l++;
else r--;
}
return new int[]{-1, -1};
}
// Dedupe sorted array in-place, return new length.
public static int dedupeSorted(int[] a) {
if (a.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < a.length; fast++) {
if (a[fast] != a[slow]) {
slow++;
a[slow] = a[fast];
}
}
return slow + 1;
}
// Classic 3Sum: all unique triplets that sum to zero.
public static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> out = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int l = i + 1, r = nums.length - 1, target = -nums[i];
while (l < r) {
int sum = nums[l] + nums[r];
if (sum == target) {
out.add(Arrays.asList(nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++; r--;
} else if (sum < target) l++;
else r--;
}
}
return out;
}
}
Complexity
- Time:
O(n) per sweep; O(n log n) dominated by sort in 3Sum - Space:
O(1) extra beyond the output list
Common pitfalls
- Forgetting to skip duplicates in 3Sum, which produces the same triplet multiple times
- Advancing neither pointer on the equality branch, causing an infinite loop
- Running two-pointer on an unsorted array without sorting first — the monotonicity argument collapses
- Using int sum where a[l]+a[r] can overflow; cast to long when values approach Integer.MAX_VALUE
- Off-by-one on the termination check (l <= r vs l < r) when the same index cannot be used twice
Key design decisions & trade-offs
- Pointer direction — Chosen: Opposed ends vs same-direction slow/fast. Opposed ends exploits sorted order for pair-sum problems; same-direction fits in-place filtering and sliding invariants. Choosing wrong forces extra state.
- Sort first or hash — Chosen: Sort + two pointers for 3Sum rather than hashmap. Sorting gives O(1) extra space and deterministic dedupe via neighbor comparison; a hashmap is O(n) memory and needs a separate dedupe pass.
- Duplicate handling — Chosen: Skip duplicates inside the inner loop. Cheaper than post-filtering with a Set and keeps the output stable-sorted. Costs a few extra comparisons per match.
Practice problems
Interview follow-ups
- Extend 3Sum to 4Sum in O(n^3) — where does the nesting stop paying off?
- Solve container-with-most-water with two pointers and prove the greedy move is optimal
- Why does the two-pointer approach break on an unsorted array, and can you recover it with an index-sort?
- Implement remove-nth-from-end of a singly linked list with a gap of n between fast and slow
- Detect a cycle in a linked list and return the cycle entry node using Floyd's tortoise-and-hare
Why it matters
Two Pointers is a core part of the Arrays & Strings toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".