Two Pointers

Two indices walking through an array can replace a whole nested loop.

beginner~60 min6 simulations14 problems

▶ guided lesson ⚡ 1-minute summary ↻ 15 recall cards

before this: Arrays & Strings · Big-O

Section

01 · why it exists

Why this exists, and the weight it carries

since?

Two pointers from both ends

Folklore: nobody is credited with inventing it. Indices that start at both ends and walk towards each other already drive the partition step of Tony Hoare's Quicksort (1961), but the interview pattern grew out of everyday practice, not one paper.

its jobs today

Sorting: quicksort's partition walks one index up from the left and one down from the right, swapping items that sit on the wrong side.
Reversing: Collections.reverse(list) walks one index from each end and swaps; StringBuilder.reverse() swaps the same mirrored pairs.
Pair search on sorted data: two items that fit a budget in a sorted price list, or two readings that add up to a threshold.

the weight it carries

Illustrative: a sorted list of 1,00,000 prices; find two that add up to ₹999. All pairs: 1,00,000 × 99,999 / 2 ≈ 5·10⁹ checks. Two pointers: at most 99,999 steps — about 50,000× fewer, and no extra memory.

without it

Every sorted-pair question falls back to O(n²) pair checks, or to O(n) extra memory for a HashSet.

when · why · how

when: Sorted input with a pair or triplet target, palindromes, reversing in place, or anything that depends on the width between two positions.
why: Each step discards one candidate for good: O(n) time and O(1) space, versus O(n²) for all pairs or O(n) memory for hashing. Sorting first adds O(n log n).
how: int l = 0, r = n - 1; while (l < r) { ... } — move exactly one side per step, based on a comparison you can justify out loud.

since?

Read / write pointers (in-place filtering)

Folklore: compacting an array in place with one index that reads and one that writes has no single inventor we could find.

its jobs today

ArrayList.removeIf first marks the elements to delete, then slides the survivors forward in one pass.
Game loops remove dead bullets and enemies from an array every frame by packing the live ones to the front — no new array, no garbage.
Cleaning data in place: dropping blank rows, repeated log lines or zero readings before the next step.

the weight it carries

Illustrative: delete 1 lakh (10⁵) zeros from an array of 10 lakh (10⁶) ints. Removing them one by one, ArrayList.remove(i)-style, shifts the tail every time: up to about 10⁵ × 10⁶ = 10¹¹ moves when the zeros sit near the front. Read/write: one pass — 10⁶ reads and at most 9·10⁵ writes.

without it

In-place filtering would mean O(n²) shifting, or a second array as big as the first.

when · why · how

when: "In place", "return the new length k", "remove / move / keep elements", or "at most k copies" in sorted data.
why: One pass: O(n) time, O(1) extra space. remove(i) in a loop is O(n²) because every removal shifts the tail.
how: int write = 0; for (int read = 0; read < n; read++) if (keep(nums[read])) nums[write++] = nums[read]; return write;

since1945

Merging two sorted sequences (one pointer each)

John von Neumann

In 1945 John von Neumann wrote a routine for the planned EDVAC computer that merges ("meshes") two sorted sequences — part of a merge-sort program. Knuth called the handwritten manuscript, kept in Herman Goldstine's files, probably the earliest surviving program for a stored-program computer. In 1970 Donald Knuth studied them in "Von Neumann's First Computer Program", and his The Art of Computer Programming credits von Neumann with merge sorting in 1945.

the problem it solvedCombining two sorted lists into one sorted list in a single pass — the step that makes merge sort O(n log n) and lets data bigger than memory be sorted in sequential passes.

its jobs today

Java's TimSort (Arrays.sort on objects, Collections.sort) finds sorted runs and merges them with one pointer per run.
Databases: a sort-merge join walks two sorted tables with one cursor each.
Storage engines built on LSM trees merge sorted files during compaction; external sort merges sorted chunks of files too big for RAM.

the weight it carries

Illustrative: two sorted order lists from two warehouses, 5 lakh each. Concatenate and sort again: about 10⁶ × log₂ 10⁶ ≈ 2·10⁷ comparisons. Merge: at most 10⁶ − 1 comparisons, in one sequential pass.

without it

Merge sort, external sorting and merge joins would all need random access or a full re-sort.

when · why · how

when: Two sorted inputs to merge, intersect or compare; "is s a subsequence of t"; merging into a buffer whose free space is at the back.
why: O(n + m) time: every comparison moves one pointer forward for good. Re-sorting would cost O((n + m) log(n + m)).
how: int i = 0, j = 0; — take the smaller head, advance its pointer, then copy the leftovers. Merging in place into the front array: start at the ends and write the larger at k--.

since1976

Three-way partition (Dutch national flag)

Edsger W. Dijkstra

Edsger Dijkstra used the Dutch national flag problem to teach how to derive a program from its invariant and prove it correct. Items of three colours — red, white and blue, like the Dutch flag — must end up grouped in flag order, using only swaps and looks. It appears in his 1976 book A Discipline of Programming; Lloyd Allison recalls hearing of it in London around 1973, so it was already going round. Later papers analysed his solutions (McMaster, CACM 1978).

the problem it solvedGrouping three kinds of items in one pass with O(1) extra memory — the same split quicksort needs when many keys equal the pivot.

its jobs today

Java's Arrays.sort(int[]) is a dual-pivot quicksort: each partition step splits the range into three zones (below, between and above two pivots) with moving pointers.
3-way quicksort keeps every key equal to the pivot in the middle zone, so data full of duplicates (ratings 1–5, status codes) still sorts fast.
Grouping by a three-way label in one pass: error / warning / info log lines, or failed / pending / successful UPI payments.

the weight it carries

Illustrative: 10 lakh (10⁶) payments tagged failed / pending / success, grouped in place. Dutch flag: one pass — at most 10⁶ looks and 10⁶ swaps, O(1) extra memory. A general sort: about 10⁶ × log₂ 10⁶ ≈ 2·10⁷ comparisons.

without it

Three-way grouping would cost a full O(n log n) sort, and a naive two-way quicksort can slow to O(n²) on inputs full of equal keys.

when · why · how

when: Exactly three groups (0/1/2, < / = / > a pivot, negative / zero / positive) and the task says one pass or O(1) space.
why: O(n) time and O(1) space in one pass, versus O(n log n) for a sort. Counting is also O(n), but needs two passes and works only on plain values.
how: int low = 0, mid = 0, high = n - 1; while (mid <= high) — 0 → swap(low++, mid++); 1 → mid++; 2 → swap(mid, high--) and look at mid again.

02 · plain english

The idea in 30 seconds

Instead of checking every pair with two nested loops (O(n²)), keep two indices and move them smartly.

Each step, one pointer moves and at least one candidate is thrown away for good — so the work is O(n).

It works when the data has order (sorted, or a clear left/right structure) that tells you which pointer to move.

picture this

A Flipkart price list sorted from cheapest to costliest, and a ₹1,000 gift card for exactly two items. Put one finger on the cheapest item and one on the costliest. Total too low? Move the cheap finger up. Too high? Move the costly finger down. Neither finger ever goes back, so one pass is enough.

03 · remember

What you must know

Opposite ends (left = 0, right = n-1, move inwards): pair sums on sorted arrays, palindromes, reversing, container problems.
Same direction (read/write or slow/fast): in-place filtering, removing duplicates, partitioning, linked-list cycles.
One pointer per sequence: two sorted inputs (merge, is-subsequence) — advance the pointer that is behind. To merge in place, fill from the back so nothing is overwritten.
Why it's correct: every move must discard something that can never be part of the answer. If you can't argue that, two pointers is the wrong tool.
Sorting first costs O(n log n) — usually still far better than O(n²), but it destroys original indices (store them first if you need them).
Loop condition is almost always while (left < right) for opposite ends — <= would compare an element with itself.
Two pointers is the parent of sliding window (same direction, with a window between the pointers).

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Reverse an array in place

The simplest opposite-ends pattern. Watch both ends become final after each swap.

loading simulation…

javajava.util.*

1class RawReverse {2    /** Reverses the array in place using two pointers that walk towards each other. */3    static void reverse(int[] nums) {4        int left = 0, right = nums.length - 1;5        while (left < right) {6            int tmp = nums[left];7            nums[left] = nums[right];8            nums[right] = tmp;9            left++;10            right--;11        }12    }13}

sim

Two Sum II — why moving one pointer is safe

Every move throws away a number that can never be part of the answer (shown grey).

loading simulation…

javajava.util.*

1class Solution {2    public int[] twoSum(int[] numbers, int target) {3        int left = 0, right = numbers.length - 1;4        while (left < right) {5            int sum = numbers[left] + numbers[right];6            if (sum == target) return new int[] {left + 1, right + 1};7            if (sum < target) left++;   // need bigger → move left up8            else right--;               // need smaller → move right down9        }10        return new int[] {-1, -1};11    }12}

sim

Container With Most Water in 3D

Bars are walls. The shorter wall limits the water — so the shorter wall is the one to drop.

loading simulation…

java

1class Solution {2    public int maxArea(int[] height) {3        int left = 0, right = height.length - 1, best = 0;4        while (left < right) {5            int h = Math.min(height[left], height[right]);6            best = Math.max(best, h * (right - left));7            // The shorter wall limits the water. Moving the taller wall can only8            // shrink the width without raising the limit — so move the shorter one.9            if (height[left] < height[right]) left++;10            else right--;11        }12        return best;13    }14}

sim

Read & write pointers (same direction)

`read` scans everything; `write` only moves when something worth keeping is found.

loading simulation…

java

1class Solution {2    public void moveZeroes(int[] nums) {3        int write = 0;4        for (int read = 0; read < nums.length; read++) {5            if (nums[read] != 0) {6                int tmp = nums[write];               // swap keeps zeros flowing right7                nums[write] = nums[read];8                nums[read] = tmp;9                write++;10            }11        }12    }13}

sim

One pointer per array — merge from the back

The free slots are at the back of nums1, so the biggest value goes there first. Nothing unread is ever overwritten.

loading simulation…

javajava.util.*

1class Solution {2    public void merge(int[] nums1, int m, int[] nums2, int n) {3        int i = m - 1, j = n - 1, k = m + n - 1;  // last value of each, last free slot4        while (j >= 0) {                          // nums2 empty → the rest of nums1 is already in place5            if (i >= 0 && nums1[i] > nums2[j]) {6                nums1[k--] = nums1[i--];          // nums1 holds the bigger value7            } else {8                nums1[k--] = nums2[j--];          // nums2's value is bigger or equal, or nums1 is used up9            }10        }11    }12}

sim

Three pointers — Dutch national flag

Three zones grow while the unknown zone in the middle shrinks to nothing.

loading simulation…

javajava.util.*

1class Solution {2    public void sortColors(int[] nums) {3        int low = 0, mid = 0, high = nums.length - 1;4        while (mid <= high) {5            if (nums[mid] == 0) {6                swap(nums, low++, mid++);          // 0 goes to the front7            } else if (nums[mid] == 1) {8                mid++;                             // 1 is already in the middle9            } else {10                swap(nums, mid, high--);           // 2 goes to the back; re-check nums[mid]11            }12        }13    }14 15    private void swap(int[] a, int i, int j) {16        int t = a[i];17        a[i] = a[j];18        a[j] = t;19    }20}

05 · cost

Time & space, explained

Two pointers vs the alternatives
	Time	Extra space	why
Brute force: check every pair	O(n²)	O(1)	n·(n−1)/2 pairs — for n = 10⁵ that is ~5·10⁹ checks, far too slow.
Sort + binary search per element	O(n log n)	O(1)–O(n)	n searches, each log n. Good, but needs the array sorted.
Hash set / map	O(n)	O(n)	One pass, but every element is stored — memory grows with input.
Two pointers (already sorted)	O(n)	O(1)	Each step moves a pointer inward; together they move at most n times.
Sort, then two pointers	O(n log n)	O(1)–O(log n)	Sorting dominates. `Arrays.sort(int[])` uses dual-pivot quicksort with O(log n) stack.
Merge two sorted arrays (one pointer each)	O(n + m)	O(1) in place	Every comparison fills one slot for good. Copy-then-sort would cost O((n + m) log(n + m)).

06 · java

Raw vs Collections Framework

Reverse: write it by hand vs use the library

javaraw two pointersjava.util.*

1class RawReverse {2    /** Reverses the array in place using two pointers that walk towards each other. */3    static void reverse(int[] nums) {4        int left = 0, right = nums.length - 1;5        while (left < right) {6            int tmp = nums[left];7            nums[left] = nums[right];8            nums[right] = tmp;9            left++;10            right--;11        }12    }13}

javaCollections / StringBuilderjava.util.*

1class LibraryReverse {2    static List<Integer> reverseList(List<Integer> list) {3        List<Integer> copy = new ArrayList<>(list);4        Collections.reverse(copy); // two pointers inside, O(n)5        return copy;6    }7 8    static String reverseString(String s) {9        return new StringBuilder(s).reverse().toString(); // O(n)10    }11}

Collections.reverse(list) and StringBuilder.reverse() swap mirrored pairs internally — O(n) time.
In interviews, write the raw version when the technique is the question; use the library when reversing is just a step.
Java String is immutable: to change characters, convert with toCharArray() or use a StringBuilder.

Same-direction pointers (read / write)

javafilter in placejava.util.*

1class ReadWrite {2    /** Keeps only even numbers, in order, in place. Returns the new length. */3    static int keepEvens(int[] nums) {4        int write = 0;                       // next slot to fill5        for (int read = 0; read < nums.length; read++) {6            if (nums[read] % 2 == 0) {7                nums[write++] = nums[read];  // copy forward8            }9        }10        return write;11    }12}

write always points to the next free slot; everything before it is the answer so far.
ArrayList.removeIf uses the same read/write compaction internally (after first marking the doomed elements in a small bitset).
Calling list.remove(i) inside a loop is the slow version: every removal shifts the whole tail, so O(n²).

Merging two sorted arrays: by hand vs the library

javaone pointer per array, from the backjava.util.*

1class Solution {2    public void merge(int[] nums1, int m, int[] nums2, int n) {3        int i = m - 1, j = n - 1, k = m + n - 1;  // last value of each, last free slot4        while (j >= 0) {                          // nums2 empty → the rest of nums1 is already in place5            if (i >= 0 && nums1[i] > nums2[j]) {6                nums1[k--] = nums1[i--];          // nums1 holds the bigger value7            } else {8                nums1[k--] = nums2[j--];          // nums2's value is bigger or equal, or nums1 is used up9            }10        }11    }12}

javaSystem.arraycopy + Arrays.sortjava.util.*

1class Solution {2    public void merge(int[] nums1, int m, int[] nums2, int n) {3        System.arraycopy(nums2, 0, nums1, m, n);  // fill the empty tail4        Arrays.sort(nums1);                       // ignores that both halves were already sorted5    }6}

The library version is two lines and fine in real code, but it throws away the fact that both parts were already sorted: O((m + n) log(m + n)).
The hand merge is O(m + n). It fills from the back because nums1's free slots are at the back.
System.arraycopy(src, srcPos, dest, destPos, length) is the fastest way to copy a block between arrays.

Java API you will actually use
call	does	cost
`Arrays.sort(int[] a)`	Sorts primitives in place (dual-pivot quicksort)	O(n log n)
`Arrays.sort(T[] a, Comparator)`	Stable sort for objects (TimSort)	O(n log n)
`Collections.reverse(list)`	Reverses a List in place	O(n)
`new StringBuilder(s).reverse()`	Reversed copy of a string	O(n)
`Character.isLetterOrDigit(c)`	True for letters and digits (skip punctuation)	O(1)
`Character.toLowerCase(c)`	Case-insensitive comparisons	O(1)
`s.charAt(i)`	Read one character without copying the string	O(1)
`System.arraycopy(src, i, dst, j, len)`	Copy a block of one array into another	O(len)
`Arrays.copyOf(a, k)`	The first k elements as a new array (handy for checking in-place answers)	O(k)
`Collections.binarySearch(list, key)`	Index of key, or −(insertion point) − 1 if it's missing	O(log n)

Pair/triplet with a target sum, array sorted

→ Opposite-ends two pointers

O(n) per scan, O(1) space.

Pair with a target sum, unsorted, must return original indices

→ HashMap<value, index>

Sorting would lose the indices; hashing is O(n).

Remove / keep elements in place

→ read/write pointers

Single pass, no extra array.

Merge two sorted arrays

→ One pointer per array (from the back when merging in place)

O(n + m) instead of O((n + m) log(n + m)) for re-sorting.

Many "is s a subsequence of t?" queries for one t

→ Per-letter index lists + Collections.binarySearch

O(|t|) once, then O(|s| log |t|) per query.

Reverse a List or String as a helper step

→ Collections.reverse / StringBuilder.reverse

Less code, same O(n).

07 · recognise

Spot the pattern

The array is sorted and you need a pair / triplet with some sum

Opposite-ends pointers

"In place", "O(1) extra space", "remove", "move", "partition"

read/write (same-direction) pointers

Palindrome, reverse, symmetric comparisons

Opposite-ends pointers comparing mirrored characters

Maximize/minimize something that depends on a width between two positions

Start widest, move the limiting side (container pattern)

Three categories to separate (0/1/2, negative/zero/positive)

Three pointers — Dutch national flag

k-Sum (3Sum, 4Sum)

Sort, fix k−2 elements with loops, two pointers for the last two

Two sorted arrays or strings to merge, compare or match in order

One pointer per sequence; merging in place → fill from the back

Squares or absolute values of a sorted array with negatives

The biggest values sit at the two ends — build the answer from the back

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

Using left <= right for pair problems: the same element would be paired with itself.
Forgetting to skip duplicates in 3Sum — you'll output the same triplet several times.
Sorting when the problem asks for original indices (LeetCode 1 Two Sum) — use a HashMap instead.
Moving the taller wall in Container With Most Water: it can never help, and you'll miss the answer.
In Dutch flag, advancing mid after swapping with high — the value swapped in hasn't been checked yet.
Merging into nums1 from the front: you overwrite nums1 values before reading them. Fill from the back.
int overflow when adding two large values: use long sum = (long) a + b if the sum can exceed Integer.MAX_VALUE (≈ 2.1·10⁹).

tricks

Say the invariant out loud in interviews: "everything left of write is final" — interviewers love it.
Before coding, prove one move: "if sum < target, nums[left] can't pair with anything, because even the largest wasn't enough."
Draw the array with arrows for left/right on paper. Dry-run 3–4 steps before writing code.
Edge cases to test: empty array, one element, all equal, all negative, answer at the very ends.
For k-Sum, the pattern stacks: 3Sum = loop + 2Sum (two pointers) → O(n²); 4Sum = 2 loops + 2Sum → O(n³).
In-place "return k" problems only check nums[0..k). Don't waste time clearing what comes after.

09 · why & how

Questions you might be too shy to ask

How do I know two pointers won't skip the right answer?

Because each move only discards elements that provably can't be in the answer. In Two Sum II, if nums[left] + nums[right] < target, then nums[left] plus anything smaller than nums[right] is even smaller — so nums[left] is useless. Discarding useless elements can never lose the answer.

Why is it O(n) when there's a while loop that looks like it could run forever?

Every iteration moves at least one pointer one step inward. The gap right − left starts at n−1 and shrinks every time, so the loop runs at most n−1 times.

Does the array always have to be sorted for two pointers?

Only when the move rule depends on order. Pair sums (Two Sum II, 3Sum) need sorting: "sum too small → move left" is only true because everything to the right is bigger. Many two-pointer problems use a different reason and never sort: a palindrome compares mirrored characters, Container moves the shorter wall, and read/write just keeps or drops each value. So ask: what fact makes this move safe? If that fact is "the array is sorted", sort first.

Why is it while (left < right) in Two Sum II but while (mid <= high) in Sort Colors?

Ask: when the two pointers are equal, is there still work to do? In Two Sum II, left == right means one number is left, and a number can't pair with itself. So stop: <. In Sort Colors, mid points at an unchecked value, and high is the last unchecked slot. When mid == high, that one value is still unchecked. So keep going: <=. Try [2, 0, 1] with < in Sort Colors and you'll see it stop one step too early.

Two pointers or a HashMap?

Sorted input (or you're allowed to sort and don't need original indices) → two pointers: O(1) space. Unsorted input where you need indices → HashMap: O(n) time, O(n) space.

What's the difference between two pointers and sliding window?

Sliding window is a special case of same-direction two pointers where you care about everything between the pointers (a window) — like the sum of a subarray. Plain two pointers usually cares only about the two elements being pointed at.

3Sum: why skip a duplicate anchor with nums[i] == nums[i - 1] and not nums[i] == nums[i + 1]?

Take [-1, -1, 2]. The answer [-1, -1, 2] needs the first -1 as the anchor and the second -1 as left. Comparing with the next value skips the first -1, so that triplet is never found. Comparing with the previous value processes the first -1 fully (it may use the second -1 as a partner) and skips only the second one — every triplet it could find was already found.

3Sum: why does the loop stop at i < n - 2, and why break once nums[i] > 0?

The anchor needs two more numbers after it, at i + 1 and n − 1. So the last useful anchor is n − 3, which is the same as i < n - 2. The array is sorted, so if nums[i] > 0, everything after it is positive too. Three positive numbers can't add up to 0, so nothing later can work.

3Sum: after finding a triplet, why move both pointers?

With nums[i] fixed, the pair at (left, right) is used up. Any other pair with the same total needs a bigger left value and a smaller right value. Moving only one side can't make a new answer. Then the skip loop jumps past lefts equal to the one just used, so [-1, 0, 1] is not added twice.

Trapping Rain Water: at left we haven't seen the bars on the right yet. How can leftMax be the right answer?

Water at a bar = min(tallest on its left, tallest on its right) − its height. We only need the smaller of the two. We move left only when height[left] < height[right]. In this scan, the taller pointer bar is always at least as tall as every bar already passed, so height[right] >= leftMax. The real right max is at least height[right], so the smaller side is the left side, and leftMax is the limit. The unseen bars on the right can only make the right side taller — never shorter.

Remove Element / Remove Duplicates: why return write, not write + 1?

write is the next free slot. So the kept values sit in 0 .. write − 1 — that's exactly write of them. Example: [3, 2, 2, 3] with val = 3. The two 2s go to slots 0 and 1, write ends at 2, and k = 2. And when read == write, nums[write++] = nums[read] copies a value onto itself. That's harmless, not a bug.

Why does write start at 1 in Remove Duplicates but at 0 in Remove Element?

In Remove Duplicates, the first value can never be a duplicate — nothing came before it. So slot 0 is kept already, and write starts at 1. In Remove Element, even the first value might be val, so nothing is kept yet: write = 0. LC 80 starts at 0 too, but its write < 2 check keeps the first two values automatically. Same idea, different rule.

Merge Sorted Array: why not merge from the front, like merge sort does?

Merge sort writes into a separate output array. Here the output is nums1 itself, and its free space is at the back. Writing at the front would overwrite nums1 values you haven't used yet. From the back, the write slot k is always ahead of i, so nothing is lost.

Do I need to memorize the code?

No — memorize the move rule and the loop condition. The code is 6–10 lines that fall out of those two decisions.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#125
Valid Palindromemust-do
EasyMetaAppleBloombergMicrosoftAmazon
#977
Squares of a Sorted Array
EasyUberMetaAmazonGoogleMicrosoft
#167
Two Sum II - Input Array Is Sortedmust-do
MediumAmazonGoogleMetaAppleAdobe
#15
3Summust-do
MediumAdobeBloombergWalmartAmazonMicrosoft+1
#16
3Sum Closest
MediumBloombergAmazonGoogleMeta
#11
Container With Most Watermust-do
MediumWalmartAmazonFlipkartBloombergTCS+1
#42
Trapping Rain Watermust-do
HardGoldman SachsWalmartSamsungAmazonByteDance / TikTok+1
#27
Remove Element
EasyBloombergGoogleMicrosoftAmazon
#26
Remove Duplicates from Sorted Array
EasyBloombergMicrosoftMetaGoogleAmazon+1
#80
Remove Duplicates from Sorted Array II
MediumAmazonMetaBloombergMicrosoft
#283
Move Zeroes
EasyTCSInfosysBloombergMetaMicrosoft+1
#88
Merge Sorted Arraymust-do
EasyMetaBloombergMicrosoftGoogleAmazon+1
#392
Is Subsequence
EasyAmazonGoogleBloomberg
#75
Sort Colorsmust-do
MediumWalmartMicrosoftTCSAmazonByteDance / TikTok+1

11 · revise

The whole chapter on one screen

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

what it is
Two indices walk the data so every step throws away candidates for good: O(n) instead of the O(n²) all-pairs loop.
use it when
Sorted array + pair or triplet sum, palindrome check, reverse in place, or keep/remove in place: think two pointers.
template
Opposite ends: l = 0, r = n - 1; while (l < r) — too small → l++, too big → r--.
template
Same direction: read scans everything, write marks the next free slot and moves only for keepers.
template
Two sorted inputs: one pointer each, take the smaller. Merging in place? Fill from the back so nothing is overwritten.
cost
O(n) time, O(1) extra space. Sorting first adds O(n log n), still far better than O(n²).
trap
l <= r pairs an element with itself. Pair problems use l < r.
trap
Sorting destroys original indices. If the answer needs them (LC 1 Two Sum), use a HashMap instead.
trap
3Sum: skip a duplicate i by comparing with the previous value, never the next one.
pro tip
Prove one move out loud: "even with the biggest value left, this one is too small, so it can never be in the answer."

12 · recall

Flip, remember, repeat

card 1 / 15

recall

Why is two pointers O(n) and not O(n²)?

tap or Space to flip ↻

Question 1: Why is two pointers O(n) and not O(n²)?

13 · check yourself

Quick quiz

Sorted array [1, 3, 5, 9], target 12, left at 1, right at 9. Sum is 10. Which pointer moves?
Why is opposite-ends two pointers O(n) and not O(n²)?
In Container With Most Water, heights are 4 (left) and 9 (right). Which wall do you discard?
LeetCode 1 Two Sum (unsorted, return original indices). Best approach?
In Dutch national flag, after swapping nums[mid] with nums[high], why don't we advance mid?
Merge Sorted Array: nums1 = [1, 4, 7, _, _] (m = 3), nums2 = [2, 9]. Which slot is filled first, and with what?
LC 80 (at most two copies): write = 4 and the kept part is [1, 1, 2, 2]. The next value is 2. Keep it?

0/0 correct · 7 left

14 · learn more