2Brute2Best
🔥0

Two Pointers Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

Keep two indexes into the data and move them toward the answer, throwing away possibilities you can prove are useless.

4 sub-patterns · 22 questions

Remember this · Two Pointers
Trigger
Sorted array, pairs/triplets with a target, comparing from both ends, compacting an array in place.
Think
If I compare the elements at two positions, can I safely discard one side?
Key question
Which pointer moves, and why can the skipped elements never be the answer?
A

What is this pattern?

Two Pointers means keeping two positions in the data and moving them on purpose, instead of trying every pair.

There are two shapes:

  • Opposite ends: one pointer starts at the left, one at the right, and they walk towards each other. Each step, one of them moves — the one that can't lead to a better answer.
  • Same direction: both pointers walk left to right. One reads every element; the other marks where the next element we want to write goes.

The trick is always the same: every move throws away options you can prove are useless, so you never need to check them.

Two people searching a sorted bookshelf for two books whose prices add up to ₹500 — one starts at the cheap end, one at the expensive end. If the pair is too cheap, the cheap-end person steps forward. If it's too expensive, the expensive-end person steps back. They never need to go back.

B

See it move

Find two numbers that add up to 10 in a sorted array. Each step throws away one number for good.

Opposite ends: move the side that can't helparr = [1, 3, 4, 6, 8, 11], target = 10step 1/6
arr
0
1
2
3
4
5
1
3
4
6
8
11
▲L
▲R
State
target
10
a[L] + a[R]
—
Start at both ends

L starts at the smallest number, R at the largest. Everything outside [L, R] will be ruled out for good.

Remove duplicates from a sorted array in place. The green region is the finished answer.

Same direction: read every element, write only the keepersnums = [1, 1, 2, 2, 2, 3, 4, 4]step 1/9
nums
0
1
2
3
4
5
6
7
1
1
2
2
2
3
4
4
▲read write
Kept so far
1
The first element is always kept

Everything before `write` is the final answer. `read` looks at each element once.

C

How do I recognise it?

  • The array is sorted (or you're allowed to sort it) and you need a pair / triplet with some sum or property.

  • You compare things from both ends: palindromes, reversing, the two ends competing (largest square, tallest wall).

  • You must change an array in place with O(1) extra space: remove, deduplicate, move zeros, compact.

  • Elements fall into a few fixed groups (0/1/2, even/odd, less/equal/greater than a pivot) and must be rearranged.

  • You walk two sequences together (is s a subsequence of t, merge two sorted lists).

Looks like Two Pointers, but isn't

Two Sum on an unsorted array, return the indices
→ Hash map

Sorting would scramble the original indices, and sorting costs O(N log N) anyway. A hash map finds the partner in one pass.

Longest / shortest subarray with some property
→ Sliding Window

Two pointers walking the same way is a window — but when you care about everything between them (a sum, a count), it's the Sliding Window pattern with its validity rule.

Subarray sum equals K
→ Prefix Sum + hash map

You need a contiguous range, not two separate elements — and with negatives no pointer move is safe.

Pair sum on an unsorted array where you need to count pairs
→ Sort first, or a hash map of counts

Opposite-end moves only make sense when the order tells you which side to move. No order → no safe move.

D

How would I discover it from scratch?

Don't memorise “use two pointers”. Ask these questions in order — the pattern falls out.

Try every pair (i, j) with two nested loops — O(N²). For triplets, three loops — O(N³).

E

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

01

Opposite ends

8 questions

One pointer at each end, walking towards each other. Each step compares the two ends and moves the side that can't do better.

02

Same direction (read / write)

5 questions

Both pointers walk left to right. read looks at every element; write is where the next element you keep goes.

03

Triplets / k-sum

6 questions

Find triplets (or quadruplets) with a target sum: sort, fix one element, and solve the rest as a two-pointer pair problem.

04

Partition / Dutch National Flag

3 questions

Rearrange elements into a few fixed groups in place. Each finished group grows behind its own pointer.

F

Don't mix these up

Opposite ends vs Same direction

Are you comparing the two ends to decide a move (opposite)? Or is one pointer just collecting what the other one reads (same direction)?

Two Pointers vs Sliding Window

If you care about two specific elements (a pair, two ends), it's two pointers. If you care about everything between them (sum, counts, distinct values), it's a sliding window.

Two Sum II (sorted) vs Two Sum (unsorted, indices)

Sorted → two pointers, O(1) space. Unsorted and you need original indices → hash map; sorting would lose the indices.

Dutch National Flag vs Stable partition

DNF swaps elements across the array, so the original order is not kept. If the problem says “keep the relative order”, use passes or fill from both ends instead.

G

Code templates (C++)

Opposite ends (sorted pair)

The comparison decides which side moves. Every move discards an element that can't be in any valid pair.

opposite-template.cpp
// Opposite ends on a sorted array: find a pair with the given sum.
// Each step throws away one element that can never be part of the answer.
pair<int, int> pairWithSum(vector<int>& a, int target) {
    int left = 0, right = (int)a.size() - 1;
    while (left < right) {
        int sum = a[left] + a[right];
        if (sum == target) return {left, right};
        if (sum < target) left++;   // need bigger: a[left] is too small for every partner
        else right--;               // need smaller: a[right] is too big for every partner
    }
    return {-1, -1};
}

Same direction (read / write)

Only the keep rule changes between problems: not equal to a value, different from the last written, not zero…

read-write-template.cpp
// Same direction (read / write): keep only the elements you want, in place.
// Everything before `write` is the final answer so far.
int keepIf(vector<int>& a, int removeValue) {
    int write = 0;
    for (int read = 0; read < (int)a.size(); read++) {
        if (a[read] != removeValue) {   // the "keep" rule changes per problem
            a[write] = a[read];
            write++;
        }
    }
    return write;   // new length: a[0 .. write-1]
}

Triplets / k-sum

Sort, fix one, two-pointer the rest. The duplicate-skipping lines are what make the triplets unique.

k-sum-template.cpp
// Triplets: sort, fix one element, then run opposite-ends two pointers on the rest.
vector<vector<int>> threeSum(vector<int> a, int target) {
    sort(a.begin(), a.end());
    vector<vector<int>> res;
    int n = a.size();
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && a[i] == a[i - 1]) continue;         // same fixed value → same triplets
        int left = i + 1, right = n - 1;
        while (left < right) {
            long long sum = (long long)a[i] + a[left] + a[right];
            if (sum < target) left++;
            else if (sum > target) right--;
            else {
                res.push_back({a[i], a[left], a[right]});
                while (left < right && a[left] == a[left + 1]) left++;    // skip duplicates
                while (left < right && a[right] == a[right - 1]) right--;
                left++, right--;
            }
        }
    }
    return res;
}

Partition (Dutch National Flag)

Three regions grow from the edges. Note when mid moves and when it doesn't.

partition-template.cpp
// Dutch National Flag: sort 0s, 1s and 2s in one pass.
// [0 .. low-1] = 0s, [low .. mid-1] = 1s, [mid .. high] = unknown, [high+1 .. n-1] = 2s
void dutchFlag(vector<int>& a) {
    int low = 0, mid = 0, high = (int)a.size() - 1;
    while (mid <= high) {
        if (a[mid] == 0) swap(a[low++], a[mid++]);   // a 0 joins the left region
        else if (a[mid] == 1) mid++;                 // a 1 is already in place
        else swap(a[mid], a[high--]);                // a 2 joins the right region; don't move mid —
                                                     // the value swapped in hasn't been checked yet
    }
}
Next
Start with Opposite ends