The pattern
How to recognise it
💡
Riya solves the same question as Aarav in the campus test. Same answer, same language. Hers passes; his times out. She used two indexes walking the array once. He used two nested loops. That is the whole difference — and it is a pattern, not a talent.
Two pointers means keeping two indexes and moving them by a rule, so a pair of loops becomes one pass. Look for these five signals.
- 1
The array is sorted and you need a pair or triplet with some property. Sorted is the giveaway: it tells you which pointer to move.
- 2
The words "in place" or "O(1) extra space" — you are being asked to overwrite the array as you walk it.
- 3
Palindrome, reverse, "from both ends" — any question that compares the front with the back.
- 4
Two sorted lists to merge, intersect or compare — one pointer per list.
- 5
A linked list where you need the middle, a cycle, or the n-th node from the end — the fast-and-slow shape.
The test: if your brute force is two nested loops over the same array, ask whether the inner loop could start where the outer one is, or come in from the other end.
Shape 1 of 3
Two ends closing in
One pointer starts at the left, one at the right, and they walk towards each other until they meet. Every turn of the loop throws away one candidate for good, so the whole thing is one pass.
Use it for: a pair that adds to a target in a sorted array, palindromes, reversing in place, container with most water, trapping rain water.
Template · Python
i, j = 0, len(a) - 1
while i < j:
# decide using a[i] and a[j] only
if need_a_bigger_value:
i += 1 # give up the smallest left value
else:
j -= 1 # give up the largest right value
Template · Java
int i = 0, j = a.length - 1;
while (i < j) {
// decide using a[i] and a[j] only
if (needABiggerValue) {
i++; // give up the smallest left value
} else {
j--; // give up the largest right value
}
}
The rule that makes it correct: every step must remove a candidate you can prove is useless. If you cannot say out loud why the value you are skipping can never be part of the answer, this shape is the wrong tool.
Shape 2 of 3
Fast and slow, same direction
Both pointers start at the left. fast reads every item; slow marks where the next kept item is written. This is how every "remove in place" question is solved.
Template · Python
slow = 0
for fast in range(len(a)):
if keep(a[fast]):
a[slow] = a[fast]
slow += 1
# a[0:slow] is the answer, slow is the new length
Template · Java
int slow = 0;
for (int fast = 0; fast < a.length; fast++) {
if (keep(a[fast])) {
a[slow] = a[fast];
slow++;
}
}
// a[0..slow-1] is the answer, slow is the new length
Shape 3 of 3
Two lists, one pointer each
i = j = 0
while i < len(a) and j < len(b): # Python
if a[i] <= b[j]: out.append(a[i]); i += 1
else: out.append(b[j]); j += 1
while i < len(a): out.append(a[i]); i += 1
while j < len(b): out.append(b[j]); j += 1
Do not forget the two tail loops. When one list runs out, the rest of the other still has to be copied. It is the most common bug in merge questions.
Problem 1 · Shape 1 EASY
Two Sum on a sorted array
You are given a sorted array and a target. Return the two positions whose values add up to the target.
Naive: try every pair with two nested loops. O(n2) time. At n = 100,000 that is 1010 steps and a guaranteed timeout.
The insight: start at both ends. If the sum is too small, the only way to get more is to move the left pointer right. If it is too big, move the right pointer left. Every move deletes one impossible candidate.
Python · verified
def two_sum(nums, target):
i, j = 0, len(nums) - 1
while i < j:
s = nums[i] + nums[j]
if s == target: return [i, j]
if s < target: i += 1
else: j -= 1
return [-1, -1]
Trace · nums = [2, 3, 6, 8, 11, 15], target = 14
i j nums[i] + nums[j] what happens
0 5 2 + 15 = 17 too big -> j = 4
0 4 2 + 11 = 13 too small -> i = 1
1 4 3 + 11 = 14 found -> return [1, 4]
Problem 2 · Shape 1 EASY
Valid palindrome
Does the text read the same backwards? Ignore anything that is not a letter or a digit, and ignore capitals. "A man, a plan, a canal: Panama" is a palindrome.
Naive: clean the string, build a reversed copy, compare. That works, and it is O(n) time — but it is O(n) extra space, and interviewers ask for O(1).
The insight: compare from both ends without building anything. When a pointer lands on a comma or a space, step over it and try again.
Python · verified
def is_palindrome(s):
i, j = 0, len(s) - 1
while i < j:
while i < j and not s[i].isalnum(): i += 1
while i < j and not s[j].isalnum(): j -= 1
if s[i].lower() != s[j].lower(): return False
i += 1
j -= 1
return True
Trace · s = "a#Ba"
i j pair what happens
0 3 a , a match -> i = 1, j = 2
1 2 # , B '#' is not alnum -> i = 2, now i == j
2 2 B , B compares with itself, matches
i > j loop ends -> return True
Checked against "race a car" (False), " " (True) and "0P" (False).
Problem 3 · Shape 2 EASY
Remove duplicates in place
A sorted array may repeat values. Keep one copy of each at the front of the same array and return how many are left. No new array allowed.
Naive: build a new list, or call remove() on every repeat. Each remove shifts the rest of the array, so that version is O(n2).
The insight: fast reads every value; slow is the next free slot at the front. Because the array is sorted, a value is new exactly when it differs from the last one you kept.
Python · verified
def remove_duplicates(nums):
if not nums: return 0
k = 1 # nums[0] is always kept
for i in range(1, len(nums)):
if nums[i] != nums[k - 1]:
nums[k] = nums[i]
k += 1
return k
Trace · nums = [1, 1, 2, 2, 2, 3, 4, 4]
i nums[i] last kept action array becomes k
1 1 1 skip 1 1 2 2 2 3 4 4 1
2 2 1 write 1 2 2 2 2 3 4 4 2
3 2 2 skip 2
4 2 2 skip 2
5 3 2 write 1 2 3 2 2 3 4 4 3
6 4 3 write 1 2 3 4 2 3 4 4 4
7 4 4 skip 4
answer: k = 4, the first four items are 1 2 3 4
Problem 4 · Shape 1 MEDIUM
Container with most water
Each number is the height of a vertical wall. Pick two walls so the water held between them is the largest. Water held = distance between them × the shorter wall.
Naive: every pair of walls, O(n2). At n = 100,000 it will not finish.
The insight: start at the two widest walls. The width can only shrink from here, so the only way to win is a taller shorter-wall. Move the shorter wall inward — moving the taller one can never help, because the short wall still caps the water and the width has gone down.
Python · verified
def max_area(height):
i, j = 0, len(height) - 1
best = 0
while i < j:
area = (j - i) * min(height[i], height[j])
if area > best: best = area
if height[i] < height[j]: i += 1
else: j -= 1
return best
Trace · height = [1, 3, 2, 4]
i j h[i] h[j] width x short = area best move
0 3 1 4 3 x 1 = 3 3 i++
1 3 3 4 2 x 3 = 6 6 i++
2 3 2 4 1 x 2 = 2 6 i++
i == j, stop. answer 6 (on [1,8,6,2,5,4,8,3,7] it returns 49)
Problem 5 · Shape 1 inside a loop MEDIUM
3Sum
Find every triplet that adds to zero. No triplet may appear twice in the answer.
Naive: three nested loops, O(n3), plus a set to kill duplicates. The insight: sort the array, fix the first number, and the rest is Two Sum on a sorted array with target -nums[i]. Skip a repeated first number, and after a hit skip repeats on both sides.
Python · verified
def three_sum(nums):
nums.sort()
res, n = [], len(nums)
for i in range(n - 2):
if nums[i] > 0: break
if i > 0 and nums[i] == nums[i - 1]: continue
lo, hi = i + 1, n - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s < 0: lo += 1
elif s > 0: hi -= 1
else:
res.append([nums[i], nums[lo], nums[hi]])
lo += 1; hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]: lo += 1
while lo < hi and nums[hi] == nums[hi + 1]: hi -= 1
return res
Trace · nums = [-1, 0, 1, 2, -1, -4]
sorted: -4 -1 -1 0 1 2
i=0 a=-4 sums are -3, -3, -2, -1 : all below 0, lo runs out
i=1 a=-1 lo=2 hi=5 -1 + -1 + 2 = 0 -> save [-1, -1, 2]
lo=3 hi=4 -1 + 0 + 1 = 0 -> save [-1, 0, 1]
i=2 a=-1 same as the previous first number -> skip
i=3 a= 0 lo=4 hi=5 0 + 1 + 2 = 3 -> too big, hi--, done
The same five in Java
Line for line the same as the Python above. Add import java.util.*; at the top of the file.
1 · Two Sum on a sorted array
int[] twoSum(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while (i < j) {
int s = nums[i] + nums[j];
if (s == target) return new int[]{i, j};
if (s < target) i++;
else j--;
}
return new int[]{-1, -1};
}
2 · Valid palindrome
boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
while (i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
while (i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
if (Character.toLowerCase(s.charAt(i))
!= Character.toLowerCase(s.charAt(j))) return false;
i++;
j--;
}
return true;
}
3 · Remove duplicates in place
int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int k = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[k - 1]) {
nums[k] = nums[i];
k++;
}
}
return k;
}
Java, continued
4 · Container with most water
int maxArea(int[] height) {
int i = 0, j = height.length - 1, best = 0;
while (i < j) {
int area = (j - i) * Math.min(height[i], height[j]);
if (area > best) best = area;
if (height[i] < height[j]) i++;
else j--;
}
return best;
}
5 · 3Sum
List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int lo = i + 1, hi = n - 1;
while (lo < hi) {
int s = nums[i] + nums[lo] + nums[hi];
if (s < 0) lo++;
else if (s > 0) hi--;
else {
res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
lo++;
hi--;
while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
}
}
}
return res;
}
The four mistakes
01Moving the wrong pointer
In container with most water, people move the taller wall. It can never help: the short wall still caps the water and the width just went down. Before you write i++, say out loud which candidate you are throwing away and why it can never win.
02Off by one in the while condition
while i < j and while i <= j are different problems. Use < when the two pointers must land on two different items — a pair, a triplet, a palindrome. With <=, Two Sum would happily return the same index twice for a target of 2 * nums[i].
03Forgetting to skip duplicates in 3Sum
Two skips are needed, not one. Skip a repeated first number before the inner loop starts, and skip repeated values on both sides after you record a hit. Miss either and [-1,-1,2] appears twice.
if i > 0 and nums[i] == nums[i - 1]: continue
while lo < hi and nums[lo] == nums[lo - 1]: lo += 1
while lo < hi and nums[hi] == nums[hi + 1]: hi -= 1
04Using two ends on unsorted data
The whole shape rests on one fact: moving the left pointer right can only raise the value. On unsorted data that is false and the answer is quietly wrong. Sort first — or, if you must return the original positions, this is a hash map problem, not a two-pointer one.
Four questions before you type. Is it sorted, or can I sort it? Do the two ends tell me which pointer to move? What am I throwing away on each move, and can I prove it is useless? Can duplicates reach my answer twice?