Log inSign up
mediumLeetCodeNot Started

Sort Colors

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.

Follow-up: Could you come up with a one-pass algorithm using only constant extra space?

Example 1 · Standard Mixed Array:

Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]
Explanation: Sorting colors in-place yields all 0s first, followed by 1s, then 2s.

Example 2 · Short Array:

Input: nums = [2, 0, 1]
Output: [0, 1, 2]
Explanation: Sorted order is [0, 1, 2].

Example 3 · Already Sorted Array:

Input: nums = [0, 1, 2]
Output: [0, 1, 2]
Explanation: Array is already partitioned.

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:

  • Two-pointer partitioning (as in QuickSort partition)
  • In-place array swaps
  • Loop invariants

What You'll Learn

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

  • Master Dijkstra's Dutch National Flag 3-way partitioning algorithm.
  • Maintain precise region invariants throughout loop iterations.
  • Understand why mid is incremented after swapping with low, but NOT after swapping with high.

Pattern Recognition Trigger

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

Signals to Look For:

  • Partitioning an array into 3 distinct values or categories in-place.
  • Requires one single pass with O(1) space.
  • Separating pivot-less elements (smaller, equal, larger).

Algorithmic Decision Tree:

  • When partitioning an array into 3 categories (0, 1, 2 or <pivot, ==pivot, >pivot): Use Dijkstra's Dutch National Flag algorithm with low, mid, and high pointers.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Standard Comparison Sort

Intuition

Sort the array using an in-place comparison sort (like Quicksort or built-in sort).

Algorithm

  1. 1. Apply standard comparison sort on the input array nums.
  2. 2. The numbers 0, 1, and 2 naturally arrange themselves in non-decreasing order.
  3. 3. Time complexity is O(N log N), which fails the linear-time requirement.

Brute Force Comparison Sorting 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 — Step 1: Pass 1, Swap 1: Compare index 0 (2) and index 1 (0)
Visual state
Values and pointers at this exact step
array
S
2
0
2
1
1
0
0
↑ i=0
1
↑ j=1
2
3
4
5
Variables at this step
i
0
j
1
Array
[0, 2, 2, 1, 1, 0]
Check / comparison
nums[0] (2) > nums[1] (0). Swap required.
Decision / next transition
Swap nums[0] and nums[1]. Array: [0, 2, 2, 1, 1, 0].
Why this step matters

Phase 1 — Step 1: Pass 1, Swap 1: Compare index 0 (2) and index 1 (0). 2 > 0, swap them.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 void sortColors(vector<int>& nums) {
17 std::sort(nums.begin(), nums.end());
18 }
19};
20
21int main() {
22 Solution sol;
23 vector<int> nums = {2, 0, 2, 1, 1, 0};
24 sol.sortColors(nums);
25 cout << "Sorted Colors: ";
26 for (int x : nums) cout << x << " ";
27 cout << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N log N) — Standard comparison sorting performs O(N log N) element comparisons.
  • Space complexity: O(1) — In-place QuickSort uses O(log N) recursion stack, or O(1) auxiliary space.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Two-Pass Counting Sort

Intuition

Count frequencies of 0s, 1s, and 2s in pass 1, then overwrite nums with the counted values in pass 2.

Algorithm

  1. 1. Initialize count0 = 0, count1 = 0, count2 = 0.
  2. 2. Pass 1: Iterate through nums and increment corresponding count.
  3. 3. Pass 2: Overwrite nums by filling count0 zeroes, then count1 ones, then count2 twos.
  4. 4. The array is sorted in O(N) time using 2 passes.

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 — Count: { 0: 2, 1: 2, 2: 2 }: Pass 1 — Frequency Count: Count each color: two 0s, two 1s, two 2s
Visual state
Values and pointers at this exact step
array
S
2
0
2
1
1
0
0
↑ Pass 1 (Count)
1
2
3
4
5
Variables at this step
Count 0
2
Count 1
2
Count 2
2
Check / comparison
Scan array to count frequencies of 0, 1, and 2.
Decision / next transition
Count: { 0: 2, 1: 2, 2: 2 }.
Why this step matters

Phase 1 — Count: { 0: 2, 1: 2, 2: 2 }: Pass 1 — Frequency Count: Count each color: two 0s, two 1s, two 2s.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 void sortColors(vector<int>& nums) {
17 int c0 = 0, c1 = 0, c2 = 0;
18 for (int num : nums) {
19 if (num == 0) c0++;
20 else if (num == 1) c1++;
21 else c2++;
22 }
23 int idx = 0;
24 while (c0--) nums[idx++] = 0;
25 while (c1--) nums[idx++] = 1;
26 while (c2--) nums[idx++] = 2;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> nums = {2, 0, 2, 1, 1, 0};
33 sol.sortColors(nums);
34 cout << "Sorted Colors: ";
35 for (int x : nums) cout << x << " ";
36 cout << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N) — Performs 2 linear traversals of size N. Total time is O(2N) = O(N).
  • Space complexity: O(1) — Requires only 3 counter variables. Space is O(1).

3. Dutch National Flag (3-Way 1-Pass Partitioning)

Intuition

Use three pointers (low, mid, high) to partition the array into 0s, 1s, and 2s in a single pass.

Algorithm

  1. 1. Initialize low = 0, mid = 0, high = nums.length - 1.
  2. 2. While mid <= high: - If nums[mid] == 0: swap(nums[low], nums[mid]), low++, mid++. - If nums[mid] == 1: mid++. - If nums[mid] == 2: swap(nums[mid], nums[high]), high-- (do not increment mid because swapped element is uninspected).
  3. 3. Array is partitioned in a single pass O(N) time and O(1) space.

Dutch National Flag 3-Way Partition Trace

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [2, 0, 2, 1, 1, 0]
Current operationSTEP 1 OF 7
Phase 1 — Step 1: Step 1 — Partition 2 to Back: nums[mid] == 2
Visual state
Values and pointers at this exact step
array
S
2
0
2
1
1
0
0
↑ low=0, mid=0
1
2
3
4
5
↑ high=5
Variables at this step
low
0
mid
0
high
4
Array
[0, 0, 2, 1, 1, 2]
Check / comparison
nums[mid] = 2. Value 2 belongs to the right end.
Decision / next transition
Swap nums[mid] (2) & nums[high] (0). Decrement high to 4.
Why this step matters

Phase 1 — Step 1: Step 1 — Partition 2 to Back: nums[mid] == 2. Swap with nums[high]. Decrement high. Do NOT increment mid yet because the swapped element is uninspected.

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

Time & Space Complexity

  • Time complexity: O(N) — Each step either increments mid or decrements high. The algorithm visits each element at most once in a single pass.
  • Space complexity: O(1) — Only uses 3 pointers (low, mid, high), requiring strictly O(1) auxiliary space.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Standard Comparison SortO(N log N)O(1)Sort the array using an in-place comparison sort (like Quicksort or built-in sort).Repeated redundant scans over the input.
2.Approach 2: Two-Pass Counting SortO(N)O(1)Count frequencies of 0s, 1s, and 2s in pass 1, then overwrite nums with the counted values in pass 2.Auxiliary memory allocation or sorting step.
3.Approach 3: Dutch National Flag (3-Way 1-Pass Partitioning)OptimalO(N)O(1)Use three pointers (low, mid, high) to partition the array into 0s, 1s, and 2s in a single pass.None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • All Identical Elements [1, 1, 1] — Input: `, Expected: ` —
  • Reverse Sorted [2, 2, 1, 1, 0, 0] — Input: `, Expected: ` —
  • Single Element Array [0] or [2] — Input: `, Expected: ` —

Interview Tips & Best Practices

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

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

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

1.What is the optimal time and auxiliary space complexity for Sort Colors?

2.Why is the brute force approach suboptimal for large inputs in Sort Colors?

3.Which data structure or technique enables the optimal solution for Sort Colors?

Back to DSA Sheet