Two PointersAlgorithmaka Lomuto partition, Hoare partition, Dutch national flag, three-way partition

Partitioning

Rearrange an array in place so that elements less than, equal to, and greater than a pivot occupy contiguous regions, using pointers that mark region boundaries.

▶ VisualizePattern: Two PointersPractice (3)
Progress

Overview

Partitioning is the workhorse inside Quick Sort and Quickselect, and a complete solution on its own for problems like Sort Colors. Given a pivot value, one linear pass rearranges the array so every element < pivot precedes every element ≥ pivot (two-way), or so the three groups < pivot, == pivot, > pivot are contiguous (three-way, the Dutch national flag problem posed by Dijkstra).

Three schemes are standard. Lomuto uses a single boundary pointer and is the easiest to get right. Hoare uses two converging pointers and does roughly three times fewer swaps on average. Dutch national flag uses three regions and handles many equal keys, which is where two-way schemes degrade to O(n²) in quicksort.

in-placeO(n)pivotquicksortthree-way

Intuition

A mental model before the formal terms.

You are sorting a shelf of books into "short" and "tall" with a single divider. Lomuto: walk left to right; each time you meet a short book, swap it into the slot right after the divider and slide the divider one to the right. Everything left of the divider is short, everything between the divider and your hand is tall, everything ahead is unsorted.

Dutch national flag with red/white/blue balls: keep a red region growing from the left, a blue region growing from the right, and examine balls in the middle. A red ball goes left, a blue ball goes right, a white ball stays. Three fences, one pass.

How it works

  1. Lomuto (pivot at a[hi]): i = lo marks the end of the < pivot region. For j from lo to hi - 1, if a[j] < pivot swap a[i] and a[j], then i++. Finally swap a[i] with a[hi]; the pivot is now at index i and in its final sorted position.
  2. Hoare (pivot value p = a[lo]): i = lo - 1, j = hi + 1. Repeat: advance i until a[i] ≥ p, retreat j until a[j] ≤ p; if i < j swap, else return j. Everything in [lo, j] is ≤ p and everything in [j+1, hi] is ≥ p; the pivot is *not* necessarily at j.
  3. Dutch national flag (values 0/1/2, or <, ==, > relative to a pivot): low = 0, mid = 0, high = n - 1. While mid ≤ high: if a[mid] == 0 swap a[low], a[mid], low++, mid++; if a[mid] == 1 mid++; if a[mid] == 2 swap a[mid], a[high], high-- (do not advance mid — the swapped-in element is unexamined).

Why it works

Lomuto invariant: at the top of each iteration, a[lo..i) are < pivot, a[i..j) are ≥ pivot, and a[j..hi) are unexamined. Both cases of the branch preserve it: a ≥ element simply extends the middle region by advancing j; a < element is swapped with the first ≥ element (at i), which extends the left region and shifts the middle region right by one. When j == hi, no unexamined elements remain, and one final swap puts the pivot between the two regions.

Dutch flag invariant: a[0..low) are 0s, a[low..mid) are 1s, a[mid..high] are unexamined, a(high..n) are 2s. Each iteration shrinks the unexamined region by exactly one index (either mid++ or high--), so the loop runs n times; when mid > high the unexamined region is empty and the three regions cover the array.

Hoare correctness: each scan stops on an element that belongs on the other side; swapping fixes both, and the pointers cross only when every element in the left part is ≤ p and every element in the right part is ≥ p. The scans cannot run off the array because the pivot itself acts as a sentinel for both directions.

Recognition

How to tell a problem wants this.

  • "Sort an array of 0s, 1s, and 2s in one pass", "sort colors", "without using the library sort", "O(1) extra space".
  • "Move all negative numbers before positive numbers", "put even numbers first", "segregate", "group by category" — two-way partition.
  • Any problem where you must implement Quick Sort or Quickselect ("find the k-th largest element in O(n) average").
  • Many duplicate keys with a pivot — three-way partition avoids the quadratic trap.
  • Statement gives an unsorted array and asks only that elements be *grouped* by a predicate, not fully sorted — full sorting would be O(n log n) where O(n) suffices.
“sorted array” → Two Pointers

Interactive visualization

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

2
0
↑lo↑mid
0
1
2
2
1
3
1
4
0
5
0
6
2
7
1
8
0
9
↑hi
1/12Three regions: a[0..lo) are 0s, a[lo..mid) are 1s, a(hi..n) are 2s, and a[mid..hi] is unknown. Initially everything is unknown.
lo (end of 0s)mid (current)hi (start of 2s)Placed 0 / 2Swapped
PseudocodeLearn Partitioning →
1lo = 0, mid = 0, hi = n - 1
2while mid <= hi:
3  if a[mid] == 0: swap(a[lo], a[mid]); lo++; mid++
4  elif a[mid] == 1: mid++
5  else: swap(a[mid], a[hi]); hi--
Variables
lo0
mid0
hi9
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1# Dutch national flag: sort values 0/1/2 in place
2low = 0, mid = 0, high = n - 1
3while mid <= high:
4  if a[mid] == 0: swap(a[low], a[mid]); low += 1; mid += 1
5  elif a[mid] == 1: mid += 1
6  else: swap(a[mid], a[high]); high -= 1   # a[mid] is now unexamined
7# Lomuto: partition a[lo..hi] around pivot a[hi]; returns pivot index
8i = lo
9for j in lo..hi-1:
10  if a[j] < a[hi]: swap(a[i], a[j]); i += 1
11swap(a[i], a[hi]); return i

Implementations

1# Sort Colors: three-way (Dutch national flag) partition of 0s, 1s and 2s in place
2def sort_colors(a: list[int]) -> None:
31 · Three region boundaries: [0,low) zeros, [low,mid) ones, (high,n) twos
4    low = 0
5    mid = 0
6    high = len(a) - 1
72 · Examine the unknown region [mid, high]
8    while mid <= high:
9        if a[mid] == 0:
103 · Zero goes to the left region; both low and mid advance
11            a[low], a[mid] = a[mid], a[low]
12            low += 1
13            mid += 1
14        elif a[mid] == 1:
154 · One is already in place; only mid advances
16            mid += 1
17        else:
185 · Two goes to the right region; mid stays because a[mid] is unexamined
19            a[mid], a[high] = a[high], a[mid]
20            high -= 1
Walkthrough
  1. Tuple assignment a[i], a[j] = a[j], a[i] is the Python swap; the right-hand side is evaluated fully before assignment.
  2. The loop mirrors the invariant: [0,low) zeros, [low,mid) ones, [mid,high] unknown, (high, n) twos.
  3. elif handles the one case with no swap.
  4. In the else branch only high moves, so the swapped-in value is examined on the next iteration.
  5. Return type None communicates in-place mutation, consistent with list.sort().
Complexity (this implementation)
time O(n) · space O(1)

Any slicing (a[:low]) would copy; the algorithm uses index assignment only.

Language notes
  • a.sort() is Timsort — O(n log n), and it would trivially "solve" the problem while missing the point.
  • The counting-sort alternative a[:] = [0] * z + [1] * o + [2] * t is two passes and rebuilds the list in place via slice assignment.
  • Python has no switch; the if / elif / else chain is the idiom (or match on 3.10+).
Common mistakes in this language
  • Rebinding a = sorted(a) inside the function — the caller keeps the unsorted list.
  • Advancing mid in the 2 branch.
  • Using while mid < high and leaving one element unexamined.
Language differences that matter here
  • Swap syntax: C++ std::swap(a[i], a[j]), JS/TS destructuring [a[i], a[j]] = [a[j], a[i]], Python tuple assignment — all in place, but only C++ is guaranteed allocation-free at the language level.
  • TypeScript can constrain the input to (0 | 1 | 2)[] at compile time; the other languages must trust or validate the data at runtime.
  • Two-way partition exists in the C++ STL (std::partition); none of the four languages ships a three-way partition, so this loop is written by hand everywhere.

Complexity

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

Lomuto: up to n swaps. Hoare: ≈ n/6 swaps on average. Three-way is essential when many keys equal the pivot.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Grouping elements by a predicate or into a small number of classes in one pass with O(1) space.
  • The partition step of Quick Sort and Quickselect.
  • Arrays with many duplicate keys — three-way partition keeps quicksort O(n log n).
  • Sort Colors and any "sort with only 3 distinct values" problem.
Avoid it when
  • You need a stable grouping (relative order within each group preserved) — Lomuto/Hoare/Dutch flag all reorder within groups; use Two Pointers (Same Direction) with an extra buffer or a stable sort.
  • More than a handful of distinct classes — use Counting Sort or a full sort.
  • Linked lists — partitioning is possible by splicing into two lists, but the index-based schemes do not apply.
  • When the data is already sorted and you only need a boundary — Binary Search finds it in O(log n).

Alternatives

Counting SortTwo Pointers (Same Direction)Quick SortQuickselect

Common mistakes

  • Dutch flag: advancing mid after swapping with high — the element brought in from the right has not been examined.
  • Dutch flag: using mid < high instead of mid <= high, leaving the last element unexamined.
  • Hoare: treating the returned index as the pivot's final position (it is not), or recursing on [lo, j-1] and [j, hi] instead of [lo, j] and [j+1, hi].
  • Hoare: using while a[i] <= pivot — with equal keys the scan can run off the end; strict comparisons plus the pivot as sentinel keep it bounded.
  • Lomuto: forgetting the final swap that places the pivot, or using <= in the comparison and getting O(n²) on all-equal arrays.

Interview patterns

  • Sort Colors (Dutch national flag) — the canonical three-pointer problem.
  • Kth Largest Element via Quickselect: partition, then recurse into one side only.
  • Partition array by parity / by sign / around a given value.
  • Implement quicksort and discuss why three-way partitioning matters for duplicate-heavy inputs.
  • Wiggle Sort II uses three-way partition around the median plus index mapping.
Interview questions on this
Mock interviews

Example problems

Move ZeroeseasySort Colors (Dutch National Flag)mediumKth Largest Element in an Arraymedium