Coding interview problems › Arrays & Hashing

#️⃣ Arrays & Hashing Medium

Sort Colors (Dutch National Flag)

Sort Colors (sort 0s, 1s and 2s) explained: Dutch National Flag three-way partition in one pass and O(1) space. Tested Python, pitfalls and a live visual.

Also searched as: Dutch national flag algorithm · sort 0s 1s and 2s · three-way partition

🔀

Try it live Free

Quicksort, Partition & Conquer

Watch the pivot snap into its final spot as smaller values move left and larger ones right. Sort Colors is that partition step with three buckets instead of two.

Also useful: Two Pointers

Open the playground →

The problem

A list contains only the values 0, 1 and 2. Rearrange it in place so all 0s come first, then 1s, then 2s, without using a library sort. Aim for a single pass.

Inputnums = [2, 0, 2, 1, 1, 0]
Output[0, 0, 1, 1, 2, 2]

The key insight

This is quicksort's partition step with pivot 1, done three ways. Keep three regions: 0s before lo, 1s between lo and mid, 2s after hi. Look at nums[mid]: a 0 swaps into the 0 region, a 2 swaps into the 2 region, a 1 just stays.

Brute force first: Counting the 0s, 1s and 2s and rewriting the list takes two passes; calling sort is O(n log n).

Step-by-step approach

  1. Set lo = mid = 0 and hi = n - 1.
  2. While mid <= hi, look at nums[mid].
  3. If it is 0: swap with nums[lo], then move both lo and mid forward.
  4. If it is 1: move mid forward.
  5. If it is 2: swap with nums[hi] and move hi back, but do not move mid, because the swapped-in value is still unchecked.

Python solution

PYTHON 3tested
def sort_colors(nums):
    lo, mid, hi = 0, 0, len(nums) - 1
    while mid <= hi:
        if nums[mid] == 0:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:                      # 2: send to the back, re-check mid
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi -= 1
    return nums

Complexity

TimeO(n)
SpaceO(1)

Every step either advances mid or shrinks hi, so there are at most n steps. Only three indices are stored.

Common mistakes

Frequently asked questions

What is the time and space complexity of Sort Colors?

The Dutch National Flag algorithm is O(n) time in one pass and O(1) extra space.

Why not increment mid after swapping with hi?

The value that came from position hi has not been inspected yet. It might be a 0 or a 2, so mid must look at it again.

Where else is three-way partitioning used?

Quicksort with many duplicate keys uses it to group values equal to the pivot, which keeps the sort fast on inputs with few distinct values.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Arrays & Hashing Hash Tables lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.