Two pointers

coreCommon atMetaAmazonGoogleMicrosoftRead firstArraysSortingPractise in the Sandbox →

Two pointers keeps two indices into the data and moves one of them per step, never backwards. Either they start at both ends and move inward, or they move in the same direction at different speeds. Each move rules out a whole group of candidates at once, so the scan is O(n) instead of checking all O(n²) pairs.

The idea in plain words

Two people are looking for a pair of books on a sorted shelf whose page counts add up to exactly 500. The slow way: pick each book and compare it with every other book. That’s every pair, O(n²).

The fast way: one person starts at the thin end, the other at the thick end. Add up their two books. Too many pages? The person at the thick end steps in, because no book could save that thickest one: even the thinnest partner already overshoots. Too few? The thin end steps in. Each step permanently discards one book and every pair it could be in.

That’s the whole trick. Two pointers work when some ordering lets you prove that one pointer’s current position can’t be part of a better answer, so you move it and never look back.

The second family uses two pointers going the same way: a fast reader that looks at every element, and a slow writer that marks where the next kept element goes. That lets you filter, compact or deduplicate an array in place with O(1) extra memory.

See it

Pick a pattern, edit the input, and step through. In the “most water” pattern, watch the grid on the right: every pair of walls is a cell. One move rules out a whole row or column of cells, which is why n − 1 scores are enough to cover all n(n−1)/2 pairs.

Two pointers, three shapes

step through

wall heights (0–99)

all pairs: row = lo, column = hi

lo0

hi8

area–

best0

pairs scored0

pairs ruled out0

current pairscoredruled out without scoringbest so farwater

9 walls means 36 possible pairs (the grid on the right). Start with the widest one: the two ends.

↺◀▶ Play▶1 / 17

When to reach for it

The problem says…	Which shape
“pair / two elements” in a sorted array (or one you may sort) with a sum, difference or bound	opposite ends, moving inward
“pick two lines / walls / heights to maximize area or score”	opposite ends: move the one that limits the score
“reverse in place”, “is it the same forwards and backwards”	opposite ends, swapping or comparing
“remove / filter / deduplicate in place”, “O(1) extra space”	same direction: reader and writer
“merge two sorted lists”, “intersection of two sorted lists”	one pointer per input, advance the smaller
squares, absolute values, or distances of a sorted array, “in sorted order”	opposite ends, fill the output from the back
linked list: middle node, cycle, k-th from the end	same direction, different speeds (fast and slow)

The precondition

Opposite-end pointers need a reason why moving one pointer can’t skip the answer. Usually that reason is sorted order or a monotone score (moving inward can only shrink width). On unsorted data with no such structure, two pointers is wrong; a hash map is usually the tool instead.

How it works

Opposite ends: shrink the search space

1. Start with lo = 0 and hi = n - 1: the widest candidate.
2. Score the pair (lo, hi) and update the best.
3. Decide which pointer cannot be part of a better pair, and move it inward. Argue it out loud: “every remaining pair that keeps this pointer is worse because…”.
4. Stop when the pointers meet.

Python

max_area.py

def max_area(heights: list[int]) -> int:
    """Two walls and the floor hold water; return the largest area. O(n) time, O(1) space."""
    lo, hi = 0, len(heights) - 1        # 1. start with the widest pair
    best = 0
    while lo < hi:
        h = min(heights[lo], heights[hi])
        best = max(best, h * (hi - lo))   # 2. score the current pair
        # 3. Move the SHORTER wall. Every pair that keeps it is narrower and no taller,
        #    so none of them can beat what we just scored: skip them all.
        if heights[lo] < heights[hi]:
            lo += 1
        else:
            hi -= 1
    return best


if __name__ == "__main__":
    assert max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49   # walls 8 and 7, width 7
    assert max_area([1, 1]) == 1
    assert max_area([5]) == 0 and max_area([]) == 0
    print("ok")

TypeScript

max_area.ts

import assert from "node:assert/strict";

/** Two walls and the floor hold water; return the largest area. O(n) time, O(1) space. */
export function maxArea(heights: number[]): number {
  let lo = 0, hi = heights.length - 1; // 1. start with the widest pair
  let best = 0;
  while (lo < hi) {
    const h = Math.min(heights[lo], heights[hi]);
    best = Math.max(best, h * (hi - lo)); // 2. score the current pair
    // 3. Move the SHORTER wall. Every pair that keeps it is narrower and no taller,
    //    so none of them can beat what we just scored: skip them all.
    if (heights[lo] < heights[hi]) lo++;
    else hi--;
  }
  return best;
}

assert.equal(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]), 49); // walls 8 and 7, width 7
assert.equal(maxArea([1, 1]), 1);
assert.equal(maxArea([5]), 0);
assert.equal(maxArea([]), 0);
console.log("ok");

C#

max_area.cs

// Two walls and the floor hold water; return the largest area. O(n) time, O(1) space.
static long MaxArea(int[] heights)
{
    int lo = 0, hi = heights.Length - 1;          // 1. start with the widest pair
    long best = 0;
    while (lo < hi)
    {
        long h = Math.Min(heights[lo], heights[hi]);
        best = Math.Max(best, h * (hi - lo));     // 2. score the current pair
        // 3. Move the SHORTER wall. Every pair that keeps it is narrower and no taller,
        //    so none of them can beat what we just scored: skip them all.
        if (heights[lo] < heights[hi]) lo++;
        else hi--;
    }
    return best;
}

if (MaxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) != 49) throw new Exception("expected 49");
if (MaxArea([1, 1]) != 1) throw new Exception("expected 1");
if (MaxArea([5]) != 0 || MaxArea([]) != 0) throw new Exception("expected 0");
Console.WriteLine("ok");

Same direction: reader and writer

1. write marks the end of the part you’re keeping. Everything before it is final.
2. read visits every element exactly once.
3. If xs[read] should be kept, copy it to xs[write] and advance write. Otherwise just advance read.
4. At the end, xs[0..write-1] is the answer and write is its length.

Python

dedupe_sorted.py

def dedupe_sorted(xs: list[int]) -> int:
    """Remove repeats from a SORTED list in place. Returns the new length k;
    xs[:k] holds the distinct values in order. O(n) time, O(1) extra space."""
    if not xs:
        return 0
    write = 1                           # 1. xs[:write] is the deduplicated prefix
    for read in range(1, len(xs)):      # 2. read scans every element once
        if xs[read] != xs[write - 1]:   # 3. new value? (sorted, so repeats are adjacent)
            xs[write] = xs[read]        #    copy it to the end of the kept prefix
            write += 1
    return write


if __name__ == "__main__":
    data = [1, 1, 2, 3, 3, 3, 7, 9, 9]
    k = dedupe_sorted(data)
    assert k == 5 and data[:k] == [1, 2, 3, 7, 9]
    assert dedupe_sorted([]) == 0
    one = [4, 4, 4]
    assert dedupe_sorted(one) == 1 and one[0] == 4
    print("ok")

TypeScript

dedupe_sorted.ts

import assert from "node:assert/strict";

/** Remove repeats from a SORTED array in place. Returns the new length k;
 *  xs.slice(0, k) holds the distinct values in order. O(n) time, O(1) extra space. */
export function dedupeSorted(xs: number[]): number {
  if (xs.length === 0) return 0;
  let write = 1; // 1. xs[0..write-1] is the deduplicated prefix
  for (let read = 1; read < xs.length; read++) { // 2. read scans every element once
    if (xs[read] !== xs[write - 1]) { // 3. new value? (sorted, so repeats are adjacent)
      xs[write++] = xs[read]; //    copy it to the end of the kept prefix
    }
  }
  return write;
}

const data = [1, 1, 2, 3, 3, 3, 7, 9, 9];
const k = dedupeSorted(data);
assert.equal(k, 5);
assert.deepEqual(data.slice(0, k), [1, 2, 3, 7, 9]);
assert.equal(dedupeSorted([]), 0);
assert.equal(dedupeSorted([4, 4, 4]), 1);
console.log("ok");

C#

dedupe_sorted.cs

// Remove repeats from a SORTED array in place. Returns the new length k;
// xs[..k] holds the distinct values in order. O(n) time, O(1) extra space.
static int DedupeSorted(int[] xs)
{
    if (xs.Length == 0) return 0;
    int write = 1;                                // 1. xs[..write] is the deduplicated prefix
    for (int read = 1; read < xs.Length; read++)  // 2. read scans every element once
        if (xs[read] != xs[write - 1])            // 3. new value? (sorted, so repeats are adjacent)
            xs[write++] = xs[read];               //    copy it to the end of the kept prefix
    return write;
}

int[] data = [1, 1, 2, 3, 3, 3, 7, 9, 9];
int k = DedupeSorted(data);
if (k != 5 || !data[..k].SequenceEqual([1, 2, 3, 7, 9])) throw new Exception("dedupe failed");
if (DedupeSorted([]) != 0) throw new Exception("empty");
if (DedupeSorted([4, 4, 4]) != 1) throw new Exception("all same");
Console.WriteLine("ok");

Opposite ends, filling an output

When the largest result always comes from one of the two ends, compare the ends, place the larger result at the back of the output, and move that pointer.

Python

sorted_squares.py

def sorted_squares(xs: list[int]) -> list[int]:
    """Squares of a SORTED list (negatives allowed), in sorted order. O(n), no re-sort."""
    out = [0] * len(xs)
    lo, hi = 0, len(xs) - 1
    for k in range(len(xs) - 1, -1, -1):   # 1. fill the output from the BACK
        # 2. The largest square is at one of the two ends: compare magnitudes.
        if abs(xs[lo]) > abs(xs[hi]):
            out[k] = xs[lo] * xs[lo]
            lo += 1                         # 3. consume the end we used
        else:
            out[k] = xs[hi] * xs[hi]
            hi -= 1
    return out


if __name__ == "__main__":
    assert sorted_squares([-7, -3, 0, 2, 5]) == [0, 4, 9, 25, 49]
    assert sorted_squares([-3, -2, -1]) == [1, 4, 9]
    assert sorted_squares([]) == []
    print("ok")

TypeScript

sorted_squares.ts

import assert from "node:assert/strict";

/** Squares of a SORTED array (negatives allowed), in sorted order. O(n), no re-sort. */
export function sortedSquares(xs: number[]): number[] {
  const out = new Array<number>(xs.length).fill(0);
  let lo = 0, hi = xs.length - 1;
  for (let k = xs.length - 1; k >= 0; k--) { // 1. fill the output from the BACK
    // 2. The largest square is at one of the two ends: compare magnitudes.
    if (Math.abs(xs[lo]) > Math.abs(xs[hi])) out[k] = xs[lo] * xs[lo++]; // 3. consume that end
    else out[k] = xs[hi] * xs[hi--];
  }
  return out;
}

assert.deepEqual(sortedSquares([-7, -3, 0, 2, 5]), [0, 4, 9, 25, 49]);
assert.deepEqual(sortedSquares([-3, -2, -1]), [1, 4, 9]);
assert.deepEqual(sortedSquares([]), []);
console.log("ok");

C#

sorted_squares.cs

// Squares of a SORTED array (negatives allowed), in sorted order. O(n), no re-sort.
static long[] SortedSquares(int[] xs)
{
    var outp = new long[xs.Length];
    int lo = 0, hi = xs.Length - 1;
    for (int k = xs.Length - 1; k >= 0; k--)      // 1. fill the output from the BACK
    {
        // 2. The largest square is at one of the two ends: compare magnitudes.
        long a = xs[lo], b = xs[hi];
        if (Math.Abs(a) > Math.Abs(b)) { outp[k] = a * a; lo++; } // 3. consume that end
        else { outp[k] = b * b; hi--; }
    }
    return outp;
}

if (!SortedSquares([-7, -3, 0, 2, 5]).SequenceEqual([0L, 4, 9, 25, 49])) throw new Exception("mixed");
if (!SortedSquares([-3, -2, -1]).SequenceEqual([1L, 4, 9])) throw new Exception("negatives");
if (SortedSquares([]).Length != 0) throw new Exception("empty");
Console.WriteLine("ok");

What it costs

	Time	Extra space
Check every pair	O(n²)	O(1)
Two pointers on sorted input	O(n)	O(1)
Sort first, then two pointers	O(n log n)	O(1) to O(n), depending on the sort
Hash map instead (unsorted, exact match only)	O(n) expected	O(n)

Why O(n): every step moves one pointer one position, and neither pointer ever moves back. Together they can take at most n steps before they meet (or before read reaches the end).

Why it’s correct: the grid in the visualization is the proof. There are n(n−1)/2 pairs. Each move discards every pair that contains the pointer being moved, and you can show none of them beats the pair just scored. So the best pair is never thrown away.

Two pointers vs a hash map is a real trade-off. If the input is already sorted, two pointers wins on memory. If it isn’t, sorting costs O(n log n) and loses the original indices, while a hash map is O(n) time but O(n) space. Say which you’re choosing and why.

Variations you’ll meet

• Nested two pointers. Fix one element with an outer loop and run a two-pointer scan on the rest: O(n²) overall instead of O(n³) for three-element conditions.
• Partitioning. Quicksort’s partition and the Dutch national flag (three regions: < pivot, = pivot, > pivot) are reader/writer patterns. See sorting.
• Fast and slow pointers. On a linked list, a pointer moving two steps for every one of the other finds the middle, and detects a cycle when they meet (Floyd’s algorithm). See linked lists.
• Two inputs. Merging two sorted arrays, or intersecting them, uses one pointer per array and always advances the one with the smaller value.
• Sliding window. When the two pointers bound a contiguous range and you track what’s inside, that’s a sliding window, the same-direction cousin with a summary attached.

Pitfalls

• Running it on unsorted data. The “move the smaller one” logic is only sound if the order lets you rule things out. Check the precondition, or sort first.
• while lo <= hi vs while lo < hi. For pairs you need two different elements, so stop when they meet: lo < hi. For “reverse in place” lo < hi is also correct (the middle element stays).
• Moving the wrong pointer, or both. Moving both at once can skip the answer. Move exactly the one you can justify.
• Duplicates. When the problem wants distinct answers, skip runs of equal values after recording a match, or you’ll report the same answer several times.
• Losing original indices. If you sort to enable two pointers but must return positions, sort (value, index) pairs.
• Overflow. Sums and products of two large ints overflow in C#. Use long (and in JS, remember numbers lose precision beyond 2⁵³).

In the interview

• Ask: “Is the input sorted? Can I sort it, or modify it in place? Do you need indices or values? Can there be duplicates?”
• Say the invariant: “Everything left of lo and right of hi has been ruled out; the answer, if it exists, is inside [lo, hi].” For reader/writer: “xs[0..write-1] is the kept output so far.”
• Justify each move with a one-sentence argument. That is the part interviewers grade.
• Compare to the alternatives: brute force O(n²); hash map O(n) time and O(n) space; two pointers O(n) time and O(1) space but needs order.
• Expect follow-ups: “Can you do it without extra memory?” (that’s usually the point of two pointers), “What if the input isn’t sorted?” (sort first and pay O(n log n), or switch tools), “What if the input is a stream?” (opposite-end pointers need random access to both ends).

Check yourself

Check yourself

pick one

In the most-water problem, heights[lo] = 3 and heights[hi] = 8. Why is it safe to move lo rather than hi?

ABecause lo is smaller than hi as an indexBEvery other pair using lo is narrower and still capped at height 3, so none can beat the current areaCBecause moving hi would make the width zeroDIt is not safe; you have to try both

Check yourself

pick one

The reader/writer dedupe on a sorted array compares xs[read] with xs[write - 1], not with xs[read - 1]. On sorted input, does that choice change the result?

AYes: comparing with xs[read - 1] keeps some duplicatesBNo: on sorted input both give the same answer, but xs[write - 1] says what you mean (the last kept value)CYes: comparing with xs[read - 1] can read out of boundsDNo, and neither works if values repeat more than twice

Check yourself

pick one

You must remove every occurrence of a value from an array in place, with O(1) extra memory, and return the new length. Order of the kept elements must not change. Which shape fits?

AOpposite ends, swapping unwanted values to the backBReader/writer in the same directionCSort first, then binary search for the valueDFast and slow pointers that meet in the middle

Practice on your own

These are classic textbook exercises, not gym questions:

• Reverse the vowels in a string in place, leaving other characters where they are.
• Move all zeros in an array to the end, keeping the order of the other elements, in place.
• Merge two sorted arrays into one sorted array.
• Given a sorted array, keep at most two copies of each value in place and return the new length.
• Find the length of the longest “mountain” (strictly up, then strictly down) in an array in one pass.

Go deeper

• Laaksonen, Competitive Programmer’s Handbook, ch. 8 “Amortized analysis”: the two pointers method and its O(n) argument.
• Sedgewick and Wayne, Algorithms, §2.3 “Quicksort”: partitioning with two pointers, including 3-way partitioning.
• Knuth, The Art of Computer Programming, Vol. 2, §3.1, exercise 6: Floyd’s cycle-finding (“tortoise and hare”) algorithm.

Related

Sliding windowSame-direction pointers that track a contiguous range.

SortingOften the step that makes two pointers possible.

Binary searchThe other way to exploit sorted order: O(log n) per query.

Linked listsFast and slow pointers for middles and cycles.