How do you sort an array of 0s, 1s, and 2s? | Interview Question

Q: How do you sort an array of 0s, 1s, and 2s?

**Target Audience:** Beginners preparing for coding interviews — no prior algorithms knowledge assumed **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First A cook has a tray of jelly beans in three flavours, red, white and blue, all mixed up in a single row, and wants them grouped: all red on the left, all white in the middle, all blue on the right. She could count each colour and then lay out a fresh row, but she has no second tray. So she uses two fingers as fences. Everything left of her left finger is red; everything right of her right finger is blue. She looks at beans one by one between the fences: a red bean gets swapped to just inside the left

The problem

Question presented to candidate: "You are given a list that contains only 0s, 1s and 2s. Sort it in place, ideally in a single pass and without calling a sort function. Please write it in Python."

What a strong answer should cover:

Counting sort (two passes, three counters) as the simple O(n) answer, then the one-pass Dutch national flag with low, mid, high.
The invariant (0s, 1s, unknown, 2s) and why mid does not advance after swapping with high.
O(n) time, O(1) extra space, exactly n loop iterations; versus O(n log n) for list.sort().
Edge cases: empty list, all one value, already sorted, reverse sorted.
Python specifics: a while mid <= high loop (a for loop cannot hold mid still), the tuple swap, and that nums[:] = [0] * c0 + [1] * c1 + [2] * c2 is in place for the caller but builds a temporary list.

Clarifying questions expected:

"Are 0, 1 and 2 the only values, and is a library sort allowed?"
"Does it have to be a single pass?"

Code / implementation expected: Yes — sort_colors(nums) in Python with three indices, mutating the list in place.

arrays
sorting
dutch-flag

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — no prior algorithms knowledge assumed Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

A cook has a tray of jelly beans in three flavours, red, white and blue, all mixed up in a single row, and wants them grouped: all red on the left, all white in the middle, all blue on the right. She could count each colour and then lay out a fresh row, but she has no second tray. So she uses two fingers as fences. Everything left of her left finger is red; everything right of her right finger is blue

The solution is hidden so you can try first

8 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonDutch national flag, traced step by step

Practice

PythonEdge cases, and Dutch flag vs counting sort on 1,000 values

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.