Two PointersAlgorithmaka read/write pointers, slow/fast index, in-place compaction, filter in place

Two Pointers (Same Direction)

A read pointer scans every element while a write pointer marks the end of the finished prefix, compacting or filtering an array in place in one pass.

▶ VisualizePattern: Two PointersPractice (3)
Progress

Overview

Same-direction two pointers is the standard way to rewrite an array in place without shifting elements one at a time. A read index i visits every element once; a write index w points to the first slot of the array that has not yet been finalized. Whenever a[i] should survive, copy it to a[w] and advance w. Because w ≤ i always, the write never clobbers an element that is still unread.

The same shape solves removing duplicates from a sorted array, deleting all occurrences of a value, moving zeroes to the end, compressing runs (string compression), and merging two sorted arrays from the back. It is the array analogue of a stable partition, and it is the inner loop of Partitioning as well.

in-placeO(n)O(1) spacestablecompaction

Intuition

A mental model before the formal terms.

Imagine a queue of people where some have to leave. Rather than asking everyone behind each departure to shuffle forward (O(n) per removal, O(n²) total), walk down the line once with a clipboard: the "write" position is the next empty spot at the front, and each person who stays steps directly into it. Nobody ever moves backward, and nobody moves twice.

The write pointer is a boundary: everything left of it is done and correct, everything from read onward is untouched input, and the gap between them is garbage that has already been copied forward.

How it works

  1. Set w = 0 (or w = 1 for remove-duplicates, since the first element always survives).
  2. For i from 0 (or 1) to n - 1: decide whether a[i] belongs in the output. The test may compare against a[w - 1] (duplicates), a constant (val, zero), or a running condition.
  3. If it belongs: a[w] = a[i] (or swap for move-zeroes so the trailing region is still valid), then w++.
  4. If it does not: do nothing — i moves on and the element is logically deleted.
  5. Return w, the new length. The prefix a[0..w) is the answer; the tail is unspecified.

Why it works

Invariant: after processing index i, the prefix a[0..w) holds exactly the kept elements from a[0..i] in their original order, and w ≤ i + 1. The base case (empty prefix) is trivial. Each step either keeps a[i] by writing it to slot w — which is safe because w ≤ i, so slot w is either i itself or a slot whose original value was already consumed — or skips it. Order is preserved because reads and writes both move left to right.

For sorted remove-duplicates, comparing a[i] with a[w - 1] is enough because all copies of a value are adjacent: if a[i] ≠ a[w-1], a[i] is strictly greater than every kept value and is therefore new.

Total work: i advances every iteration, so exactly n reads and at most n writes. O(n) time, O(1) extra space, and the algorithm is stable.

Recognition

How to tell a problem wants this.

  • The statement says "in-place", "modify the array in place", "with O(1) extra memory", or "return the new length k; the first k elements must hold the result".
  • "Remove duplicates from a sorted array", "remove all instances of val", "move all zeroes to the end while maintaining relative order", "compress the string in place".
  • "Merge two sorted arrays where nums1 has enough trailing space" — same idea, but walking backward from the end so unread elements are never overwritten.
  • Any one-pass filter or run-length encoding that must not allocate a second array.
  • You are copying elements into a new list one by one and the interviewer asks "can you do it without extra space?"
“sorted array” → Two Pointers

Interactive visualization

Play, step, change the input. ← → and space work too.

1
0
1
1
↑write↑read
2
2
3
3
3
4
3
5
5
6
7
7
7
8
9
9
1/20Remove duplicates in place. a[0] is always unique, so write starts at 1: everything before write is the deduplicated prefix.
write pointerread pointerUnique prefixDuplicate (skipped)
PseudocodeLearn Two Pointers (Same Direction) →
1write = 1
2for read in 1 .. n-1:
3  if a[read] != a[write-1]:
4    a[write] = a[read]
5    write += 1
6return write  # length of unique prefix
Variables
write1
read1
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1w = 0
2for i in 0..n-1:
3  if keep(a[i]):        # e.g. a[i] != 0, or i == 0 or a[i] != a[w-1]
4    a[w] = a[i]          # w <= i, so nothing unread is overwritten
5    w = w + 1
6return w                 # a[0..w) is the compacted result

Implementations

1# Remove Duplicates from Sorted Array: compact in place, return the new length k
2def remove_duplicates(a: list[int]) -> int:
31 · Handle the empty array
4    if not a:
5        return 0
62 · The first element always survives; write pointer starts at 1
7    w = 1
83 · Read pointer scans every remaining element
9    for i in range(1, len(a)):
104 · Keep a[i] only if it differs from the last kept value
11        if a[i] != a[w - 1]:
12            a[w] = a[i]
13            w += 1
145 · a[0..w) holds the unique values
15    return w
Walkthrough
  1. if not a is the idiomatic empty check for lists.
  2. range(1, len(a)) starts the read pointer at index 1; w = 1 reflects that a[0] is already kept.
  3. The list is mutated in place through index assignment — Python lists are mutable references.
  4. Comparing against a[w - 1] rather than a[i - 1] is the key correctness detail after the first skip.
  5. Return w; del a[w:] would physically shorten the list in O(n - w) if the caller wants that.
Complexity (this implementation)
time O(n) · space O(1)

Slicing (a[:w]) copies and would cost O(w) extra memory; del a[w:] truncates in place.

Language notes
  • list(dict.fromkeys(a)) deduplicates while preserving order, but allocates a new list (not in place).
  • del a[w:] or a[w:] = [] truncates in place; a = a[:w] rebinds a copy and the caller keeps the old list.
  • itertools.groupby yields runs of equal adjacent values — an alternative view of the same sorted-dedup problem.
Common mistakes in this language
  • Calling a.remove(x) or a.pop(i) in a loop — both are O(n) per call.
  • Rebinding a = a[:w] inside the function and expecting the caller to see the change.
  • Using set(a) and losing order (and the in-place contract).
Language differences that matter here
  • C++ has this algorithm built in as std::unique + erase; JS/TS/Python have order-preserving dedup idioms ([...new Set(a)], dict.fromkeys) but none of them work in place.
  • Truncation after compaction: C++ a.resize(w), JS/TS a.length = w, Python del a[w:] — all O(1) or O(n - w), none of them copy the kept prefix.
  • Element deletion inside a loop is quadratic in every language (erase, splice, pop(i)); the write pointer exists precisely to avoid it.

Complexity

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Exactly n reads; writes ≤ n. Stable with respect to kept elements.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • In-place filtering, deduplication, or compaction with O(1) extra space.
  • Run-length encoding / string compression where output is never longer than input.
  • Merging into an array that has trailing free space (walk from the back).
  • Any single pass where output position lags input position.
Avoid it when
  • The output can be longer than the input (e.g. expanding abbreviations) — a forward write pointer would overwrite unread data; write backward or use a new buffer.
  • Elements must be reordered non-locally (sorting) — this is a filter, not a sort.
  • The keep/drop decision depends on elements *after* i that have not been read yet — you need a lookahead or a second pass.
  • Immutable inputs (strings in Java/Python/JS) — convert to a mutable array first or just build a new one.

Alternatives

Two Pointers (Opposite Ends)PartitioningSliding Window (Variable Size)Stack

Common mistakes

  • Starting w = 0 for remove-duplicates and comparing a[i] with a[i - 1] instead of a[w - 1] — after the first skip a[i-1] may be a value that was overwritten.
  • For move-zeroes, assigning a[w] = a[i] without zeroing/swapping — non-zero values get duplicated and zeros vanish.
  • Returning the array instead of the new length w, or forgetting that the tail beyond w is garbage.
  • Merging two sorted arrays forward into nums1 and overwriting unread values — walk from the end.
  • Trying to use it for unsorted deduplication; adjacent comparison only finds duplicates when equal values are contiguous.

Interview patterns

  • Remove Duplicates from Sorted Array (I and II: allow at most k copies by comparing with a[w - k]).
  • Remove Element / Move Zeroes / segregate even and odd.
  • String Compression: read runs with i, write char + count at w.
  • Merge Sorted Array from the back: p1, p2, and w = m + n - 1.
  • Backspace String Compare: apply # in place with a write pointer, then compare.
  • Sort Colors is this technique with two write pointers — see Partitioning.
Interview questions on this
Mock interviews

Example problems

Remove Duplicates from Sorted ArrayeasyMove ZeroeseasySort Colors (Dutch National Flag)medium