DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Sort Colors

mediumTwo pointers Must-do

Problem statement

You are given a list nums where every value is exactly 0, 1, or 2 — think of them as three colors: red, white, and blue. Rearrange the list in place so that all the 0s come first, then all the 1s, then all the 2s.

You must do this without calling a general-purpose sort function — the point of the problem is to use the fact that there are only three distinct values to sort in a way that's faster than a generic comparison sort.

This maps directly onto grouping servers, jobs, or log lines by a small fixed set of states — for example herding hosts by health status (0 = healthy, 1 = degraded, 2 = down) into three visible blocks for a dashboard, in place, without extra memory.

Examples

Example 1

Input: nums = [2,0,2,1,1,0]

Output: [0,0,1,1,2,2]

Explanation: The array has two 0s, two 1s, and two 2s. Sorting them in place puts all the 0s first, then all the 1s, then all the 2s.

Example 2

Input: nums = [2,0,1]

Output: [0,1,2]

Explanation: There is exactly one of each color, so the sorted array is simply [0, 1, 2].

Hints

Approach

Optimal: Dutch National Flag, one pass

Intuition

Split the array into three regions as you scan it once: a region of 0s at the front, a region of 1s in the middle, and a region of 2s at the back, with an unprocessed region still to be examined in between. Keep three pointers: low marks the boundary where the next 0 should go, high marks the boundary where the next 2 should go, and mid is the element currently being looked at.

At mid: if it's a 0, it belongs in the 0-region, so swap it with the element at low and advance both low and mid. If it's a 1, it's already in the right place relative to what's been processed, so just move mid forward. If it's a 2, swap it with the element at high and move high back — but don't advance mid yet, because the element swapped in from the back hasn't been examined.

Steps

  1. Set low = 0, mid = 0, high = n - 1.
  2. While mid <= high:
    • If nums[mid] == 0: swap nums[low] and nums[mid], then increment both low and mid.
    • Else if nums[mid] == 1: just increment mid.
    • Else (nums[mid] == 2): swap nums[mid] and nums[high], then decrement high only (leave mid where it is).
  3. When mid passes high, every element has been placed in its region and the array is sorted.

Dry run

nums = [2, 0, 2, 1, 1, 0]

low mid high nums[mid] action array
0 0 5 2 swap mid,high; high-- [0, 0, 2, 1, 1, 2]
0 0 4 0 swap low,mid; low++, mid++ [0, 0, 2, 1, 1, 2]
1 1 4 0 swap low,mid (same spot); low++, mid++ [0, 0, 2, 1, 1, 2]
2 2 4 2 swap mid,high; high-- [0, 0, 1, 1, 2, 2]
2 2 3 1 mid++ [0, 0, 1, 1, 2, 2]
2 3 3 1 mid++ [0, 0, 1, 1, 2, 2]

mid (4) now exceeds high (3), so the loop ends with [0, 0, 1, 1, 2, 2], matching the expected output.

Edge cases: when nums[mid] is 2 and gets swapped with nums[high], mid deliberately does not advance, because the newly-swapped-in value at mid hasn't been checked yet — advancing early would skip examining it. An array of a single element (or all one color) finishes in one or zero swaps.

Complexity

Time O(n) — Every element is looked at once, and the three pointers only ever move forward (`low` and `mid` increase, `high` decreases), so the total number of steps is bounded by the length of the array. This is a single pass instead of the two passes counting sort needs, though both are technically O(n).

Space O(1) — Only three integer pointers are used, no matter the array's size.

class Solution:
    def sortColors(self, nums: list[int]) -> None:
        low, mid, high = 0, 0, len(nums) - 1
        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1


if __name__ == "__main__":
    a = [2, 0, 2, 1, 1, 0]
    Solution().sortColors(a)
    print(a)  # [0, 0, 1, 1, 2, 2]

    b = [2, 0, 1]
    Solution().sortColors(b)
    print(b)  # [0, 1, 2]

Follow-up questions

Use the counting approach's idea without its second scan over the original array: count the 0s, 1s, and 2s in the single read-only pass, then build a brand-new output array (or emit values one at a time) using those counts. This trades away the "sort in place with no extra space" property but still solves the problem in O(n) time with a single read pass — a reasonable trade when the input truly can't be mutated.

Not with just low/mid/high — that trick is specific to exactly three groups. The cleanest fix is to fall back to the counting approach generalized to four buckets (count0 through count3), which stays O(n) time with one counting pass and one writing pass, at the cost of no longer being a single pass. Extending the pointer trick itself to four groups gets fiddly enough that it's rarely worth it over just adding a bucket to counting sort.

RecapThe whole problem in a few lines, for the night before
  • Spot it: an array holding only a small, fixed set of distinct values (here, 0/1/2) that needs sorting
  • Idea: three pointers — low/mid/high — partition the array into 0s, 1s and 2s in one pass (Dutch National Flag); swap 0s to the front, 2s to the back, leave 1s in place
  • Cost: O(n) time, O(1) space (counting sort: O(n) time but two passes, O(1) space)
  • Trap: after swapping nums[mid] with nums[high], don't advance mid — the newly swapped-in value hasn't been checked yet

Frequently asked questions

The technique is named after Edsger Dijkstra, who described it using the three horizontal stripes of the Dutch flag (red, white, blue) as the three regions the array gets partitioned into. It's a general pattern for partitioning an array into three groups in a single pass, not just for literal colors.

Because the value that just got swapped into position mid came from the unexamined end of the array and hasn't been checked yet — it could be a 0, 1, or 2. If mid advanced immediately, that value would be skipped entirely and might end up in the wrong region. Advancing low and mid together after a 0-swap is safe for a different reason: the value swapped down from mid to low is guaranteed to be a 1 (everything at or before the current mid, other than the just-seen 0, has already been classified), so it's fine for mid to move past it too.

Not directly with three pointers — the technique relies on there being exactly three known categories to partition into. For more categories, counting sort (this page's "better" approach, generalized to more buckets) still works in O(n + k) time for k distinct values, but the single-pass three-pointer trick specifically needs three groups.

It tests whether a candidate recognizes when a small, fixed set of values makes a generic O(n log n) sort wasteful, and whether they can reason correctly about in-place pointer manipulation without off-by-one bugs — the same care needed when compacting or partitioning a large in-memory buffer (like separating healthy, degraded, and failed nodes) without allocating a second array.