Sort Colors (Dutch National Flag)

Table of Contents +

This one looks like a normal sorting question. But it is not. The array only has three kinds of values: 0, 1, and 2. The interviewer knows you can call a sort function. What they really want to see is whether you can sort it in a single pass, touching each element only once.

🎨 The Problem

You are given an array that holds only 0s, 1s, and 2s. Think of them as colors. Red is 0. White is 1. Blue is 2. Your job is to arrange them so all the 0s come first, then all the 1s, then all the 2s.

Here is what that looks like:

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

The follow-up the interviewer adds is the real test. Do it in one pass. And do not use a counting sort. So you cannot count how many 0s, 1s, and 2s there are and then refill the array. You have to sort it as you walk through it just once.

🧠 The Simple Idea First

The obvious way is counting. You go through the array once and count how many 0s, 1s, and 2s you saw. Then you go through the array again. You write that many 0s, then that many 1s, then that many 2s.

This works. It is O(n) time too. But it walks the array twice. The interviewer asked for one pass. So this is the version you mention out loud, then you say “but we can do better”.

🚩 The Dutch National Flag Way

Here is the smart trick. It is called the Dutch National Flag algorithm, named after the flag’s three colored bands. The idea is to split the array into three regions as you go. The 0s go on the left. The 2s go on the right. The 1s settle in the middle on their own.

You keep three markers:

low marks where the next 0 should go. Everything before low is already 0.
high marks where the next 2 should go. Everything after high is already 2.
mid is the one that actually moves through the array and looks at each value.

Think of three buckets being filled from both ends. Riya pushes every red box to the far left. Arjun pushes every blue box to the far right. Whatever is left in the middle is white, and it is already where it belongs.

The key is what mid does with each value:

If array[mid] is 0, swap it with array[low]. Move both low and mid forward.
If array[mid] is 1, it is already in the middle. Just move mid forward.
If array[mid] is 2, swap it with array[high]. Move high backward. Do not move mid.

That last rule confuses people. When you swap a 2 to the back, the value that comes from high is brand new. You have not looked at it yet. So you must check mid again before moving on. That is why mid stays put after a 2 swap.

Steps to sort the array in one pass

Let’s write the steps down before any code.

Set low = 0, mid = 0, and high = n - 1, where n is the number of elements.
While mid is less than or equal to high:
- If array[mid] is 0, swap array[low] and array[mid], then do low = low + 1 and mid = mid + 1.
- If array[mid] is 1, just do mid = mid + 1.
- If array[mid] is 2, swap array[mid] and array[high], then do high = high - 1 only.
When mid passes high, the array is sorted.

Don't move mid after a 2 swap

When you swap a 2 to the back, you pull an unseen value into mid from the high side. If you move mid forward right away, you skip checking that value. So leave mid where it is and look at it again on the next loop.

Code to sort colors in one pass

Now let’s see it in every language.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

# sort an array of 0s, 1s, and 2s in one pass
def sort_colors(arr):
    low = 0
    mid = 0
    high = len(arr) - 1

    while mid <= high:
        if arr[mid] == 0:
            # send the 0 to the low region
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == 1:
            # 1 belongs in the middle, just move on
            mid += 1
        else:
            # send the 2 to the high region, recheck mid
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1

def main():
    arr = [2, 0, 2, 1, 1, 0]
    sort_colors(arr)
    print("Sorted colors:", arr)

if __name__ == "__main__":
    main()

The output of the above code will be:

Sorted colors: [0, 0, 1, 1, 2, 2]

⏱️ Time and Space Complexity

Approach	Time	Space
Counting sort (two pass)	O(n)	O(1)
Dutch National Flag (one pass)	O(n)	O(1)

Both ways are O(n) time and O(1) space. So what is the real difference? The counting way reads the array twice. The Dutch National Flag way reads it once, and sorts as it reads. That single pass is the part the interviewer is testing.

Say the pattern out loud

This problem is a three-way partition. Naming it in the interview shows you have seen the pattern before. It is the same idea used inside three-way quick sort to handle lots of repeated values.

🧩 Key Takeaways

✅ Sort Colors asks you to sort only 0s, 1s, and 2s, in one pass, without counting.
✅ The Dutch National Flag algorithm uses three pointers: low, mid, and high.
✅ A 0 goes to the low side, a 2 goes to the high side, and a 1 stays in the middle.
✅ After swapping a 2 to the back, you do not move mid, because the new value is unseen.
✅ Time is O(n) and extra space is O(1).

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Now that the three pointer partition makes sense, try these next:

Move All Zeros to the End uses a similar pointer trick to push values to one side.
Quick Sort uses partitioning as its core idea, just like this problem.

Sort Colors is a favorite because it hides a real technique behind a simple-looking question. Once the three pointers click, the whole family of partition problems gets easier.

Previous Find a Peak Element Next Kth Largest Element

Share & Connect

Share on LinkedIn