Contest problems reward recognising a shape fast. Two pointers is the first shape worth learning, because it costs nothing: no second array, no dictionary, no recursion. Two int variables and the array you were given.
This is part 1 of ten, five patterns each. Every program below is complete, was run on .NET 10, and its output is pasted from the run.
Running these
.NET 10 runs a single .cs file with no project, no class and no Main:
dotnet run twopointers.csThat is new, and it is the fastest way to try any of this. Everything on this page is written that way.
Pattern 1 — Closing in from both ends
You have a sorted array. Find two values that add up to a target.
The obvious version tries every pair. On a six-element array that is fine. Count what it actually does:
int[] a = [2, 7, 11, 15, 19, 26];
int target = 30;
int bruteSteps = 0;
for (int i = 0; i < a.Length; i++)
for (int j = i + 1; j < a.Length; j++)
{
bruteSteps++;
if (a[i] + a[j] == target) goto done;
}
done:
int twoPtrSteps = 0;
int lo = 0, hi = a.Length - 1;
while (lo < hi)
{
twoPtrSteps++;
int sum = a[lo] + a[hi];
if (sum == target) break;
if (sum < target) lo++; else hi--;
}
Console.WriteLine($"n = {a.Length}");
Console.WriteLine($"every pair : {bruteSteps} pairs examined");
Console.WriteLine($"two pointers : {twoPtrSteps} steps");It prints:
n = 6
every pair : 11 pairs examined
two pointers : 4 stepsEleven pairs against four steps is not an interesting gap. At n = 100000 it is five billion against a hundred thousand, and that is the whole contest.
Here is the move. The array is sorted, so a[hi] is the largest value still in play. If a[lo] + a[hi] is too small, then a[lo] has no partner anywhere — you just paired it with the biggest thing available and still fell short. So a[lo] cannot be part of any answer. Throw it away and never look at it again.
Same logic mirrored: if the sum is too big, a[hi] is too big for everything left, so drop it.
Two pointers closing in from both ends of a sorted array. A greyed cell has been ruled out and is never looked at again.
int[] a = [2, 7, 11, 15, 19, 26];
int target = 30;
int lo = 0, hi = a.Length - 1;
while (lo < hi)
{
int sum = a[lo] + a[hi];
string move = sum == target ? "= target, stop"
: sum < target ? "< target, lo++"
: "> target, hi--";
Console.WriteLine($"lo={lo} hi={hi} {a[lo],2} + {a[hi],2} = {sum,2} {move}");
if (sum == target) break;
if (sum < target) lo++; else hi--;
}
Console.WriteLine($"\nindices ({lo}, {hi}) -> values ({a[lo]}, {a[hi]})");It prints:
lo=0 hi=5 2 + 26 = 28 < target, lo++
lo=1 hi=5 7 + 26 = 33 > target, hi--
lo=1 hi=4 7 + 19 = 26 < target, lo++
lo=2 hi=4 11 + 19 = 30 = target, stop
indices (2, 4) -> values (11, 19)Each step throws away exactly one index and never reconsiders it. There are n indices, so there are at most n steps. That is why it is linear, and it is worth saying in that form rather than as “the pointers meet in the middle” — the discarding is the reason, the meeting is just what it looks like.
Cost: O(n) time after the sort, O(1) space.
Reach for it when the input is sorted or you can afford to sort it, and moving lo right makes your quantity bigger while moving hi left makes it smaller. That monotonicity is the entire requirement. Without it the discarding step is invalid and the whole thing quietly returns wrong answers.
Pattern 2 — The write pointer
Remove the duplicates from a sorted array in place, and report how many values are left.
The tempting version builds a List<int>, adds the keepers, and copies back. It is correct. It also allocates a second array, and at 10⁶ elements that allocation is the difference between passing and not.
Both pointers move the same way here. r reads every cell. w marks where the next kept value goes. The reason nothing gets destroyed is that w can never overtake r — w only advances when r does, and it starts behind.
One array, two jobs. r reads every cell, w marks where the next kept value goes. w never overtakes r, so nothing is overwritten before it has been read. Everything past w at the end is stale and ignored.
int[] a = [1, 1, 2, 2, 2, 3, 4, 4, 5];
Console.WriteLine($"before: [{string.Join(", ", a)}]\n");
int w = 1;
for (int r = 1; r < a.Length; r++)
{
if (a[r] == a[w - 1])
{
Console.WriteLine($"r={r} a[r]={a[r]} {$"same as a[{w - 1}]",-12} skip w stays {w}");
continue;
}
a[w] = a[r];
w++;
Console.WriteLine($"r={r} a[r]={a[r]} {"new value",-12} a[{w - 1}]={a[r]} w -> {w}");
}
Console.WriteLine($"\nkept {w}: [{string.Join(", ", a[..w])}]");
Console.WriteLine($"tail : [{string.Join(", ", a[w..])}] <- stale, and that is fine");It prints:
before: [1, 1, 2, 2, 2, 3, 4, 4, 5]
r=1 a[r]=1 same as a[0] skip w stays 1
r=2 a[r]=2 new value a[1]=2 w -> 2
r=3 a[r]=2 same as a[1] skip w stays 2
r=4 a[r]=2 same as a[1] skip w stays 2
r=5 a[r]=3 new value a[2]=3 w -> 3
r=6 a[r]=4 new value a[3]=4 w -> 4
r=7 a[r]=4 same as a[3] skip w stays 4
r=8 a[r]=5 new value a[4]=5 w -> 5
kept 5: [1, 2, 3, 4, 5]
tail : [3, 4, 4, 5] <- stale, and that is fineLook at the tail. [3, 4, 4, 5] is left sitting there, stale. That is not a bug to clean up — writing over it would cost another pass for no benefit. The contract is that the answer is a[..w], and everything past w is none of the caller’s business.
Cost: O(n) time, O(1) space.
Reach for it when the problem says in place, or return the new length, or without allocating. Compacting, filtering and partitioning by a predicate are all this pattern wearing different words.
Pattern 3 — Sort, anchor, scan
Find every triple that sums to zero, with no triple reported twice.
Three nested loops is O(n³) and will not pass. But fix the first value and look at what is left: find two values summing to -a[i]. That is pattern 1, exactly. Sorting once up front costs O(n log n) and buys the monotonicity that pattern 1 needs.
The genuinely fiddly part is not the search, it is the duplicates. They have to be skipped in two different places, for two different reasons:
- A repeated anchor. If
a[i] == a[i-1], every triple starting atiwas already found starting ati-1. Skip the anchor entirely. - A repeated
loorhiafter a hit. Having recorded a triple, walk both pointers past any copies of the values just used, or the very next iteration reports the same triple again.
Sort once, then fix one value and run two pointers over what is left. Skipping a repeated anchor is what stops the same triplet being reported twice.
int[] a = [-1, 2, -4, -1, 1, 0];
Array.Sort(a);
Console.WriteLine($"sorted: [{string.Join(", ", a)}]\n");
List<(int, int, int)> found = [];
for (int i = 0; i < a.Length - 2; i++)
{
if (i > 0 && a[i] == a[i - 1])
{
Console.WriteLine($"anchor i={i} a[i]={a[i],2} duplicate anchor, skip");
continue;
}
int lo = i + 1, hi = a.Length - 1;
Console.WriteLine($"anchor i={i} a[i]={a[i],2} need a[lo] + a[hi] == {-a[i]}");
while (lo < hi)
{
int sum = a[i] + a[lo] + a[hi];
Console.WriteLine($" lo={lo} hi={hi} {a[i],2} + {a[lo],2} + {a[hi],2} = {sum,2}");
if (sum == 0)
{
found.Add((a[i], a[lo], a[hi]));
while (lo < hi && a[lo] == a[lo + 1]) lo++;
while (lo < hi && a[hi] == a[hi - 1]) hi--;
lo++; hi--;
}
else if (sum < 0) lo++;
else hi--;
}
}
Console.WriteLine();
foreach (var t in found) Console.WriteLine($"triplet: {t}");It prints:
sorted: [-4, -1, -1, 0, 1, 2]
anchor i=0 a[i]=-4 need a[lo] + a[hi] == 4
lo=1 hi=5 -4 + -1 + 2 = -3
lo=2 hi=5 -4 + -1 + 2 = -3
lo=3 hi=5 -4 + 0 + 2 = -2
lo=4 hi=5 -4 + 1 + 2 = -1
anchor i=1 a[i]=-1 need a[lo] + a[hi] == 1
lo=2 hi=5 -1 + -1 + 2 = 0
lo=3 hi=4 -1 + 0 + 1 = 0
anchor i=2 a[i]=-1 duplicate anchor, skip
anchor i=3 a[i]= 0 need a[lo] + a[hi] == 0
lo=4 hi=5 0 + 1 + 2 = 3
triplet: (-1, -1, 2)
triplet: (-1, 0, 1)The anchor at i=2 is skipped without a single inner step, because -1 already had its turn at i=1. That skip is what makes the output a set rather than a list with repeats in it.
Cost: O(n²) time — n anchors, each running a linear scan — plus the sort. O(1) space beyond the output.
Reach for it when you need a fixed-size combination satisfying a condition. Four-sum is this again with one more loop outside.
Pattern 4 — Send every value to its own index
An array holds n values in the range 1..n. One value appears twice, one is missing. Find both, using no extra memory.
A HashSet<int> solves it and costs O(n) memory. The sum-of-values trick gets you one equation and you need two. But look at the constraint again: the values are 1..n and the array is length n. The array is a hash table, and the hash function is v - 1.
So put every value where it belongs. Value 3 goes to index 2. If two values want the same home, the array stops being able to move, and the cell that never got filled tells you what is missing.
The loop is a while, not a for, and that matters. After a swap, index i holds a different value that has not been placed yet, so i must not advance. It advances only once the value at i is home.
Cyclic sort sends every value to the index it belongs at. When two values want the same home the array stops moving, and whatever is left out of place names both the duplicate and the missing number.
int[] a = [3, 1, 5, 4, 3, 2];
Console.WriteLine($"start: [{string.Join(", ", a)}] values are 1..{a.Length}\n");
int i = 0;
while (i < a.Length)
{
int home = a[i] - 1;
if (a[i] != a[home])
{
Console.WriteLine($"i={i} a[i]={a[i]} belongs at index {home}, which holds {a[home]} swap");
(a[i], a[home]) = (a[home], a[i]);
Console.WriteLine($" -> [{string.Join(", ", a)}]");
}
else
{
Console.WriteLine($"i={i} a[i]={a[i]} is already home (or its twin is) i++");
i++;
}
}
Console.WriteLine($"\nsorted as far as it can be: [{string.Join(", ", a)}]\n");
for (int j = 0; j < a.Length; j++)
if (a[j] != j + 1)
Console.WriteLine($"index {j} holds {a[j]}, should hold {j + 1} -> duplicate = {a[j]}, missing = {j + 1}");It prints:
start: [3, 1, 5, 4, 3, 2] values are 1..6
i=0 a[i]=3 belongs at index 2, which holds 5 swap
-> [5, 1, 3, 4, 3, 2]
i=0 a[i]=5 belongs at index 4, which holds 3 swap
-> [3, 1, 3, 4, 5, 2]
i=0 a[i]=3 is already home (or its twin is) i++
i=1 a[i]=1 belongs at index 0, which holds 3 swap
-> [1, 3, 3, 4, 5, 2]
i=1 a[i]=3 is already home (or its twin is) i++
i=2 a[i]=3 is already home (or its twin is) i++
i=3 a[i]=4 is already home (or its twin is) i++
i=4 a[i]=5 is already home (or its twin is) i++
i=5 a[i]=2 belongs at index 1, which holds 3 swap
-> [1, 2, 3, 4, 5, 3]
i=5 a[i]=3 is already home (or its twin is) i++
sorted as far as it can be: [1, 2, 3, 4, 5, 3]
index 5 holds 3, should hold 6 -> duplicate = 3, missing = 6That looks like it could be quadratic — a loop with a swap inside that sometimes does not advance. It is not. Every swap puts at least one value in its permanent home, and a value that is home is never moved again. There are n values, so there are at most n swaps in the entire run.
When the values are a permutation of a known range, the array is already a hash table and you are allowed to use it as one.
Cost: O(n) time, O(1) space.
Reach for it when the problem says values from 1 to n, or from 0 to n, and asks for a missing or duplicated one. That phrasing is the tell, and it is doing you a favour by being there.
Pattern 5 — Three regions in one pass
Sort an array containing only 0, 1 and 2. One pass, no comparison sort.
Counting each value and rewriting works, and it is two passes. It also does not generalise, which is the real objection — the version below is how you partition around a pivot when there are many equal keys, which is what stops quicksort degrading on duplicate-heavy input.
Three indices carve the array into four regions. Everything left of low is a settled 0. Everything right of high is a settled 2. Between mid and high is the part nobody has looked at yet, and it shrinks by one every iteration.
The whole algorithm is these three rules plus one invariant: everything left of low is a 0, everything right of high is a 2, and the unknown region shrinks by one on every iteration. That last rule is the one people get wrong — the value swapped back from high has never been examined, so mid must not move past it.
Read that third rule again, because it is the one that gets written wrong. When you swap a[mid] with a[high], the value that arrives at mid came from the unexamined region. Nobody has tested it. Advance mid past it and you have shipped an untested value into the settled 1s. Advancing mid on the 0 case is fine for the opposite reason: the value that arrives came from low, and everything before mid has already been tested.
int[] a = [2, 0, 2, 1, 1, 0, 2, 1, 0];
Console.WriteLine($"start: [{string.Join(", ", a)}]\n");
int low = 0, mid = 0, high = a.Length - 1;
while (mid <= high)
{
switch (a[mid])
{
case 0:
(a[low], a[mid]) = (a[mid], a[low]);
Console.WriteLine($"a[mid]=0 swap into the 0s low {low}->{low + 1} mid {mid}->{mid + 1} high {high} [{string.Join(", ", a)}]");
low++; mid++;
break;
case 1:
Console.WriteLine($"a[mid]=1 already correct low {low} mid {mid}->{mid + 1} high {high} [{string.Join(", ", a)}]");
mid++;
break;
default:
(a[mid], a[high]) = (a[high], a[mid]);
Console.WriteLine($"a[mid]=2 swap into the 2s low {low} mid {mid} high {high}->{high - 1} [{string.Join(", ", a)}]");
high--;
break;
}
}
Console.WriteLine($"\ndone: [{string.Join(", ", a)}]");It prints:
start: [2, 0, 2, 1, 1, 0, 2, 1, 0]
a[mid]=2 swap into the 2s low 0 mid 0 high 8->7 [0, 0, 2, 1, 1, 0, 2, 1, 2]
a[mid]=0 swap into the 0s low 0->1 mid 0->1 high 7 [0, 0, 2, 1, 1, 0, 2, 1, 2]
a[mid]=0 swap into the 0s low 1->2 mid 1->2 high 7 [0, 0, 2, 1, 1, 0, 2, 1, 2]
a[mid]=2 swap into the 2s low 2 mid 2 high 7->6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=1 already correct low 2 mid 2->3 high 6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=1 already correct low 2 mid 3->4 high 6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=1 already correct low 2 mid 4->5 high 6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=0 swap into the 0s low 2->3 mid 5->6 high 6 [0, 0, 0, 1, 1, 1, 2, 2, 2]
a[mid]=2 swap into the 2s low 3 mid 6 high 6->5 [0, 0, 0, 1, 1, 1, 2, 2, 2]
done: [0, 0, 0, 1, 1, 1, 2, 2, 2]Nine values, nine iterations, and it never compares two array elements to each other.
Cost: O(n) time, O(1) space, and it is stable in the sense that matters here — one pass, no recursion.
Reach for it when you are partitioning into three groups by a cheap test on each element. The classic framing is the flag colours; the useful framing is less than pivot, equal to pivot, greater than pivot.
What to remember
-
Opposite ends needs monotonicity, not just sortedness. Moving
loright must push your quantity one way and movinghileft must push it the other. Check that before you trust the discard. -
Two pointers in the same direction is the in-place edit.
wtrailsr, so nothing is overwritten before it has been read, and the stale tail pastwis deliberate. -
A repeated anchor and a repeated pointer are two different duplicate bugs. Fixing one does not fix the other, and only one of them is visible in a small test case.
-
1..nin the problem statement means the array can be its own hash table. O(1) space instead of O(n), and the swap loop is linear because every swap settles a value forever. -
After swapping in from
high,midstays put. The value you just received has never been examined. This is one character of difference and it is the most common bug in the whole pattern.
Part 2 takes the same two-index idea and makes both pointers travel in the same direction, where the gap between them is the answer: sliding windows, and the at-most-K trick that turns “exactly K” into a subtraction.