Log inSign up
mediumLeetCodeNot Started

Dutch National Flag

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function and in one single pass using constant extra memory.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Explanation: The sorted color array groups all 0s (red) first, 1s (white) second, and 2s (blue) last.

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]
Explanation: Elements rearranged from mixed colors to ascending order [0, 1, 2].

Example 3:

Input: nums = [0]
Output: [0]
Explanation: Single element array is already sorted.

Constraints:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] is either 0, 1, or 2.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array indexing and two-pointer swap techniques
  • Understanding loop invariants
  • Partitioning concepts in Quick Sort

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master Dijkstra's Dutch National Flag algorithm and 3-way partitioning.
  • Understand loop invariants and pointer mechanics in multi-pointer array manipulation.
  • Recognize why mid must NOT advance when swapping with high (unexamined element transferred).
  • Apply 3-way partitioning to optimize QuickSort against duplicate-heavy datasets.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sorting an array with a fixed, small set of distinct values (e.g. 3 distinct values 0, 1, 2).
  • In-place reordering requirement with O(1) auxiliary memory.
  • Single-pass partitioning requirement without extra counting arrays.

Algorithmic Decision Tree:

  • If values are arbitrary -> Standard Comparison Sort O(N log N).
  • If values are small integers and 2 passes are allowed -> Counting Sort (Count 0s, 1s, 2s then overwrite).
  • If strictly 1 pass and O(1) auxiliary space -> 3-Pointer Dutch National Flag algorithm (low, mid, high).

Connected Patterns:

Quick Sort 3-Way Partitioning (handling duplicates)Sort Array by Parity (2-way partitioning)Wiggle Sort

1. Brute Force (Built-in Comparison Sort)

Intuition

Passes the array into built-in sorting routines. While it satisfies the output format, it violates the single-pass linear time constraint.

Algorithm

  1. Step 1: Call standard library sort on nums.
  2. Step 2: Return or mutate in place.

Brute Force (Built-in Comparison Sort) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 0, 2, 1, 1, 0]
Current operationSTEP 1 OF 6
Phase 1 — Setup: Left pointer L anchors at 0
Visual state
Values and pointers at this exact step
pointers
S
2
0
2
1
1
0
0
↑ L (Anchor)↑ R (Scan)
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Current Value
2
Valid Prefix Count
0
Check / comparison
arr[0]=2. Evaluate condition on first element.
Decision / next transition
Setup invariant: left pointer guards valid prefix.
Why this step matters

Phase 1 — Setup: Left pointer L anchors at 0. Scanner pointer R starts traversing the array.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 void sortColors(std::vector<int>& nums) {
8 std::sort(nums.begin(), nums.end());
9 }
10};
11
12int main() {
13 Solution sol;
14 std::vector<int> nums = {2, 0, 2, 1, 1, 0};
15 sol.sortColors(nums);
16 std::cout << "Sorted: ";
17 for (int x : nums) std::cout << x << " ";
18 std::cout << std::endl;
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force (Built-in Comparison Sort).
  • Space complexity: O(1) — Space complexity for Brute Force (Built-in Comparison Sort).

Why Brute Force Doesn't Scale:

For huge arrays streamed or stored in cache lines, making multiple passes evicts cache lines. A one-pass partition guarantees minimal memory bus traffic and zero extra allocation.

With N = 10,000,000 values of categorical labels (e.g. Low, Medium, High priority packets in a network router), single-pass DNF partitions packets at line rate without buffering.

2. Better (Two-Pass Counting Sort)

Intuition

Since the only possible values are 0, 1, and 2, we can count their frequencies in O(N). In a second pass, we fill the array with count0 zeroes, then count1 ones, and count2 twos.

Algorithm

  1. Step 1: Initialize c0 = 0, c1 = 0, c2 = 0.
  2. Step 2: Iterate through nums and increment respective counters.
  3. Step 3: Iterate index i from 0 to nums.length - 1. Overwrite with 0 while c0 > 0, then 1 while c1 > 0, then 2.

Better (Two-Pass Counting Sort) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 0, 2, 1, 1, 0]
Current operationSTEP 1 OF 6
Phase 1 — Setup: Left pointer L anchors at 0
Visual state
Values and pointers at this exact step
pointers
S
2
0
2
1
1
0
0
↑ L (Anchor)↑ R (Scan)
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Current Value
2
Valid Prefix Count
0
Check / comparison
arr[0]=2. Evaluate condition on first element.
Decision / next transition
Setup invariant: left pointer guards valid prefix.
Why this step matters

Phase 1 — Setup: Left pointer L anchors at 0. Scanner pointer R starts traversing the array.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 void sortColors(std::vector<int>& nums) {
7 int c0 = 0, c1 = 0, c2 = 0;
8 for (int x : nums) {
9 if (x == 0) c0++;
10 else if (x == 1) c1++;
11 else c2++;
12 }
13 int idx = 0;
14 while (c0-- > 0) nums[idx++] = 0;
15 while (c1-- > 0) nums[idx++] = 1;
16 while (c2-- > 0) nums[idx++] = 2;
17 }
18};
19
20int main() {
21 Solution sol;
22 std::vector<int> nums = {2, 0, 2, 1, 1, 0};
23 sol.sortColors(nums);
24 std::cout << "Two-Pass Sorted: ";
25 for (int x : nums) std::cout << x << " ";
26 std::cout << std::endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better (Two-Pass Counting Sort).
  • Space complexity: O(N) — Space complexity for Better (Two-Pass Counting Sort).

3. Optimal (One-Pass 3-Pointer Dutch National Flag)

Intuition

We maintain the invariant: - nums[0 ... low-1] are 0s - nums[low ... mid-1] are 1s - nums[mid ... high] are unclassified - nums[high+1 ... n-1] are 2s

Loop until mid > high: 1. If nums[mid] == 0: swap(nums[low], nums[mid]), low++, mid++ 2. If nums[mid] == 1: mid++ 3. If nums[mid] == 2: swap(nums[mid], nums[high]), high-- (do NOT increment mid because the swapped element from high hasn't been checked!)

Algorithm

  1. Step 1: Initialize low = 0, mid = 0, high = nums.length - 1.
  2. Step 2: While mid <= high:
  3. - Case nums[mid] == 0: swap(nums[low], nums[mid]), low++, mid++.
  4. - Case nums[mid] == 1: mid++.
  5. - Case nums[mid] == 2: swap(nums[mid], nums[high]), high--.
  6. Step 3: Array is sorted in-place in exactly one pass.

3-Pointer Partitioning on [2, 0, 2, 1, 1, 0]

2 of 2 questions left today
Step 1 / 8
Trace timeline13% explored
InputINPUT nums = [nums = [2, 0, 2, 1, 1, 0]]
Current operationSTEP 1 OF 8
Phase 1 — Step 1: Step 1
Visual state
Values and pointers at this exact step
array
S
nums = [2, 0, 2, 1, 1, 0]
0
↑ i (Step 1)
Variables at this step
Current Phase
1
Inspected Value
nums = [2, 0, 2, 1, 1, 0]
Condition Met
false
Running Status
Evaluating
Why this step matters

Phase 1 — Step 1: Step 1

Step 1 / 8
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 void sortColors(std::vector<int>& nums) {
8 int low = 0, mid = 0, high = (int)nums.size() - 1;
9
10 while (mid <= high) {
11 if (nums[mid] == 0) {
12 std::swap(nums[low], nums[mid]);
13 low++;
14 mid++;
15 } else if (nums[mid] == 1) {
16 mid++;
17 } else { // nums[mid] == 2
18 std::swap(nums[mid], nums[high]);
19 high--;
20 // Note: Do NOT increment mid here!
21 }
22 }
23 }
24};
25
26int main() {
27 Solution sol;
28 std::vector<int> nums = {2, 0, 2, 1, 1, 0};
29 sol.sortColors(nums);
30 std::cout << "DNF Sorted: ";
31 for (int x : nums) std::cout << x << " ";
32 std::cout << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal (One-Pass 3-Pointer Dutch National Flag).
  • Space complexity: O(1) — Space complexity for Optimal (One-Pass 3-Pointer Dutch National Flag).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Built-in Sort)O(N log N)O(1) to O(N)Use built-in Dual-Pivot QuickSort or Timsort to sort the array.Comparison sort lower bound Omega(N log N).
2.Better (Two-Pass Counting Sort)O(N)O(1)Pass 1: Count total occurrences of 0, 1, and 2. Pass 2: Overwrite nums with count0 zeroes, count1 ones, and count2 twos.Requires two passes through memory.
3.Optimal (One-Pass 3-Pointer Dutch National Flag)OptimalO(N)O(1)Use 3 pointers (low, mid, high) to maintain partition invariants in a single pass in-place.Theoretical minimum O(N) scan limit.

Common Pitfalls & Crucial Edge Cases

Incrementing mid on swap with high

When nums[mid] == 2, swapping with nums[high] brings an untested element from high to mid. If you increment mid, that new element is skipped and may stay out of place.

Using mid < high instead of mid <= high

If the middle element at mid == high is 0 or 2, terminating early leaves that last element in the wrong partition.

Failing to swap in-place

Creating a new array or returning an array copy violates the O(1) memory and in-place mutation requirement.

Crucial Edge Cases to Validate:

  • All Identical Elements ([0,0,0] or [2,2,2]): The algorithm correctly leaves the array unchanged without index out-of-bounds.
  • Already Sorted Array ([0,1,2]): Pointers low and mid advance smoothly without unnecessary high swaps.
  • Reverse Sorted Array ([2,1,0]): Tests that swapping 2 to the right and subsequently swapping 0 to the left preserves order correctly.
  • Single Element Array ([1] or [0]): While mid <= high executes once and terminates immediately.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the loop invariant clearly at the start of the interview.
  2. Explicitly highlight why mid is not incremented when swapping with high. Interviewers look for this exact edge case reasoning.
  3. Mention that this is the core building block for 3-way QuickSort (Dijkstra's dual-pivot optimization).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we NOT increment mid when nums[mid] == 2 after swapping with nums[high]?

2.What is the loop invariant for the Dutch National Flag algorithm?

3.What is the time complexity of the Dutch National Flag 3-way partition?

Back to DSA Sheet