Move a pointer only when you can say which candidates the move eliminates and why none of them could be the answer. If you cannot say it, the solution is a guess, and a brute-force cross-check will usually find the counterexample quickly.
Two families: opposite ends and same direction
Opposite-end pointers start at index 0 and n − 1 and move toward each other. They need structure to reason about: usually a sorted array, or a quantity such as width that shrinks predictably. Same-direction pointers both start on the left. A read pointer visits every element while a write pointer marks where the next kept element goes, or a fast pointer takes two steps for each step of a slow pointer to find a linked list's middle or detect a cycle.
Both families are O(n) for one reason: each pointer moves only one way, so together they make O(n) moves. The extra space is O(1), which is often the real requirement hiding in the prompt: “in place,” “constant extra memory,” or “without a hash map.” If the input is unsorted and you must return original indices, a hash map is often the better tool.
| Variant | Start | Precondition | Typical problems |
|---|---|---|---|
| Opposite ends | 0 and n − 1 | Sorted, or a monotonic quantity | Pair sum, container with most water |
| Read / write | Both at the start | Order to preserve | Remove duplicates, move zeros |
| Fast / slow | Both at the head | Linked structure | Middle node, cycle detection |
| Anchor + pair | Loop index, then two pointers | Sorted copy | 3-sum, 3-sum closest |
Pair sum in a sorted array, and why each move is safe
With the array sorted ascending, compare nums[lo] + nums[hi] with the target. If the sum is too small, nums[lo] cannot belong to any answer: its largest remaining partner is nums[hi], and even that is not enough. So lo moves right. If the sum is too large, nums[hi] is eliminated by the mirror argument and hi moves left. Each step removes one index from consideration and never removes an index that belongs to a solution.
The script prints (2, 3, 5) for target 10: indices 2 and 3 hold 4 and 6, found after five comparisons. Target 13 has no pair, and the loop stops after five steps with (None, None, 5). The total is at most n − 1 comparisons. Say this elimination argument in one sentence during the interview; it separates a recalled answer from an understood one.
def pair_sum(nums, target):
"""nums must be sorted ascending. Returns (i, j, steps)."""
lo, hi, steps = 0, len(nums) - 1, 0
while lo < hi:
steps += 1
s = nums[lo] + nums[hi]
if s == target:
return lo, hi, steps
if s < target:
lo += 1 # nums[lo] is too small for every remaining partner
else:
hi -= 1 # nums[hi] is too large for every remaining partner
return None, None, steps
nums = [1, 3, 4, 6, 8, 11]
print(pair_sum(nums, 10))
print(pair_sum(nums, 13))Container with most water: moving the shorter side
Pick lines lo and hi; the area is (hi − lo) × min(height[lo], height[hi]). Suppose height[lo] is the shorter one. Any other container that keeps lo and pairs it with an index between them is narrower, and its height is still capped by height[lo]. None of them can beat the area just measured, so lo can be discarded. No such argument covers the taller line: paired with a tall line between the two, it can still form a bigger container, so discarding it may skip the optimum.
The script prints 49 49: the two pointer answer matches brute force on the standard input, where lines of height 8 and 7 stand seven positions apart. The True on the second line comes from 2,000 random arrays checked against the O(n²) version with a fixed seed. Run a cross-check like this whenever you invent or half-remember a greedy pointer rule. On ties either side may move, since the discarded line is still the shorter or equal one.
import random
def max_area(height):
lo, hi, best = 0, len(height) - 1, 0
while lo < hi:
best = max(best, (hi - lo) * min(height[lo], height[hi]))
if height[lo] < height[hi]:
lo += 1 # the shorter line has no better partner left
else:
hi -= 1
return best
def brute(height):
n = len(height)
return max((j - i) * min(height[i], height[j])
for i in range(n) for j in range(i + 1, n))
h = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(max_area(h), brute(h))
rng = random.Random(7)
cases = [[rng.randint(0, 50) for _ in range(rng.randint(2, 30))]
for _ in range(2000)]
print(all(max_area(c) == brute(c) for c in cases))Same direction: remove duplicates in place
The invariant is that nums[:write] holds the unique values seen so far, in order. The read pointer scans every element; when it finds a value different from the last kept one, it copies the value to nums[write] and advances write. Because the input is sorted, duplicates are adjacent, so comparing with nums[write − 1] is enough. The function runs in O(n) time with O(1) extra space.
The output is 5 [0, 1, 2, 3, 4], and the full list prints as [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]. The tail is leftover data, not an error: the contract is that only the first k positions are meaningful. Say so aloud, because an interviewer may ask whether you need to clear the rest. The same read/write skeleton moves zeros to the end and filters values in place.
def dedupe_sorted(nums):
"""Compact unique values to the front in place; return their count."""
if not nums:
return 0
write = 1 # nums[:write] holds unique values
for read in range(1, len(nums)):
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return write
a = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k = dedupe_sorted(a)
print(k, a[:k])
print(a)3-sum: when sorting first changes the complexity
Sorting costs O(n log n), so it pays off only when it unlocks something better than the alternative. For 3-sum the brute force is O(n³). Sorting once, then fixing each anchor and running opposite-end pointers on the rest, gives O(n²), and the sort disappears into that term. Duplicates become easy too: equal values sit next to each other, so skipping a repeated anchor or middle value removes duplicate triples without a set.
The script prints [[-1, -1, 2], [-1, 0, 1]], then [[0, 0, 0]] for four zeros, then [] when no triple sums to zero. For plain pair sum on unsorted input the trade-off reverses: a hash set finds a pair in O(n) average time, while sorting first costs O(n log n) and loses the original indices. sorted() builds a new list, an O(n) copy; list.sort() works in place but mutates the caller's data.
def three_sum(nums):
nums = sorted(nums) # O(n log n), less than the O(n^2) scan
out = []
for i in range(len(nums) - 2):
if i and nums[i] == nums[i - 1]:
continue # same anchor, same triples
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s < 0:
lo += 1
elif s == 0:
out.append([nums[i], nums[lo], nums[hi]])
lo += 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1 # skip repeated middle values
else:
hi -= 1
return out
print(three_sum([-1, 0, 1, 2, -1, -4]))
print(three_sum([0, 0, 0, 0]))
print(three_sum([1, 2, -2, -1]))| Problem | Without sorting | Sort + two pointers |
|---|---|---|
| Pair sum, return indices | Hash map, O(n) average | O(n log n), indices lost unless stored |
| Pair sum, input already sorted | Hash map, O(n) extra space | O(n) time, O(1) space |
| 3-sum, unique triples | O(n³) brute force | O(n²), duplicates skipped by order |
| Pair sum closest to target | O(n²) brute force | O(n log n) |
Translating to Java, and explaining the solution aloud
In Java the pattern is identical, but two details deserve a sentence. First, nums[lo] + nums[hi] on int values can overflow: the Java Language Specification says an overflowing integer addition keeps only the low-order bits, so a large positive sum can turn negative and send a pointer the wrong way. Widen to long before adding when the sum can leave the int range. Second, the Java 21 documentation describes Arrays.sort(int[]) as a dual-pivot quicksort that offers O(n log n) performance on all data sets.
When you explain any pointer solution, use three beats: the precondition (sorted input or a monotonic quantity), the invariant (what lies between or behind the pointers), and the elimination argument for each move. Then trace a tiny input by hand. Common slips are writing lo <= hi when a pair needs two distinct indices, forgetting to skip duplicates after recording a triple, and sorting an array whose original indices the prompt asks you to return.
Practice set and next steps
Rebuild each solution from its invariant rather than from memory of the code. Good variations: count every pair with a given sum, 3-sum closest, move zeros while preserving order, and a palindrome check that skips non-alphanumeric characters. For each one, write the one-sentence elimination argument first. If you cannot, run a brute-force comparison like the one above before trusting the rule.
For the surrounding patterns, use the data structures and algorithms question set and the Python interview guide, and pick a platform from the practice roundup for timed drills.
Quick answers
Frequently asked questions
Do two pointer problems always require a sorted array?
No. Same-direction pointers, such as read/write compaction or fast/slow cycle detection, need no sorting. Opposite-end pointers need some monotonic structure: sorted values for pair sum, or a width that only shrinks, as in the container problem.
What is the difference between two pointers and sliding window?
A sliding window is a same-direction two pointer scheme that also maintains a summary of the elements between the pointers, such as a sum or a frequency map. Opposite-end pointers keep no such window state.
Why is 3-sum O(n²) and not O(n² log n)?
The sort runs once, before the loops, for O(n log n). After that, each of the n anchors runs one linear pointer pass, so the total is O(n log n + n²), which is O(n²). Sorting inside the anchor loop is the mistake that adds a log factor.
Is the fast and slow pointer technique the same idea?
It shares the same-direction structure but uses a different argument. Inside a cycle the fast pointer gains one node per step on the slow one, so the gap must reach zero and they meet. Without a cycle, the fast pointer reaches the end first.
Source notes
References and review policy
Information checked on November 7, 2026. Section links identify sources for factual claims and technical explanations. Interpretations, practice scenarios and preparation recommendations are RecallDeck’s editorial work.
From reading to recall
Practice the full interview loop.
RecallDeck schedules the concepts you miss and keeps coding, design, and behavioral fundamentals available when the interviewer changes direction.