DSA interview question

Sort an Array of 0s, 1s and 2s (Dutch National Flag)

Medium · Algorithms · Topics: array, two pointer, sorting

The problem

A factory line produces parts tagged 0 (reject), 1 (rework) or 2 (pass), and before shipping they must be grouped in that order: all 0s, then all 1s, then all 2s. The line can only swap parts in place and should do it in a single pass. A general sort is O(n log n) and ignores the fact that there are only three values; counting takes two passes. Dijkstra's Dutch National Flag algorithm does it in one pass with three pointers.

Example: [2, 0, 2, 1, 1, 0] → [0, 0, 1, 1, 2, 2].

Function signature

void sortColors(vector<int>& a);  // values are 0, 1 or 2; sorts in place in one pass

Test cases

Input `a`	Output	Explanation
`[2, 0, 2, 1, 1, 0]`	`[0, 0, 1, 1, 2, 2]`
`[2, 0, 1]`	`[0, 1, 2]`
`[0]`	`[0]`
`[1, 1, 1]`	`[1, 1, 1]`	Only 1s
`[2, 2, 0, 0]`	`[0, 0, 2, 2]`	No 1s
`[]`	`[]`

(Confirm: only the values 0, 1 and 2 appear; in place, one pass, O(1) extra space.)

How interviewers phrase it

"Sort colors: red, white and blue as 0, 1 and 2" (LeetCode 75).
"Sort an array of 0s, 1s and 2s without using a sort function."
"Can you do it in one pass with constant space?"

Clarifying questions to ask

Are the values only 0, 1 and 2?
Is one pass required, or are two passes acceptable?
In place?

Follow-ups to expect

"What's the two-pass solution?"
"What do the three pointers mean?"
"Why don't you advance mid after swapping with high?"
"Why is it safe to advance mid after swapping with low?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview