TRT
Sign in
mediumCoreLeetCode#three-way partition#Dutch national flag

Sort colors

Sort an array of 0s, 1s and 2s in one pass and in place, with a three-way (Dutch national flag) partition.

The Runtime Theory Team1 min read
Taught inQuick sort and partitioningPro — members onlyPartition the array around a pivot so that smaller elements come first, then sort each side. Quick sort is O(n log n) on average, works in place, and with good pivots and a fallback it never hits its O(n²) worst case.
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

innums = [2, 0, 2, 1, 1, 0]

out[0, 0, 1, 1, 2, 2]

innums = [2, 0, 1]

out[0, 1, 2]

innums = [0]

out[0]

Given an array with values 0, 1 and 2 (red, white and blue), sort it in place so that equal values are adjacent and in the order 0, 1, 2, without using a library sort.

Before you code

Counting sort works in two passes. The one-pass version partitions around the value 1 into three regions: less than, equal to and greater than the pivot, exactly the three-way partition quick sort uses for duplicates.

Hints

  1. Keep three indexes: low (end of the 0s), mid (current element) and high (start of the 2s).
  2. If nums[mid] is 0, swap it with nums[low] and advance both. If it is 1, advance mid. If it is 2, swap it with nums[high] and decrease high, without advancing mid: the swapped-in value hasn't been examined.
  3. Stop when mid > high.

Production & complexity notes

When solving Sort colors on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Quick sort and partitioning to reinforce the underlying pattern.

What it practices

The three-way partition, from Quick sort and partitioning.

More practice in this track

hard · dsaDesign a skip listmedium · dsaDesign a bounded blocking queueeasy · dsaRange sum query: immutable

Not started

Sign in to save your learning progress.

Sign in to save