.png)
Sort an Array of 0s, 1s, and 2s
Problem Statement
You are given an array consisting only of 0s, 1s, and 2s.
Your task is to sort the array in ascending order without using any built-in sorting function.
This problem is also known as the Dutch National Flag Problem.
Example 1
Input
arr = [0, 2, 1, 2, 0]
Output
[0, 0, 1, 2, 2]
Example 2
Input
arr = [2, 2, 1, 0, 1, 0]
Output
[0, 0, 1, 1, 2, 2]
Why This Problem Is Important
- Very frequently asked in interviews
- Tests:
- Array traversal
- In-place modification
- Pointer manipulation
- Foundation for partitioning algorithms
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force (Sorting) | O(n log n) | O(1) |
| Approach 2 | Counting Method | O(n) | O(1) |
| Approach 3 | Dutch National Flag Algorithm | O(n) | O(1) |
Approach 1: Brute Force (Using Sorting)
Idea
Simply sort the array using a standard sorting algorithm.
Algorithm
- Apply any comparison-based sorting algorithm
- Return the sorted array
Time & Space Complexity
- Time: O(n log n)
- Space: O(1)
Implementations
C Implementation
#include
#include
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int main() {
int arr[] = {0, 2, 1, 2, 0};
int n = 5;
qsort(arr, n, sizeof(int), compare);
for(int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
C++ Implementation
#include
#include
using namespace std;
int main() {
int arr[] = {0, 2, 1, 2, 0};
int n = 5;
sort(arr, arr + n);
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Java Implementation
import java.util.Arrays;
public class Sort012 {
public static void main(String[] args) {
int[] arr = {0, 2, 1, 2, 0};
Arrays.sort(arr);
for(int num : arr)
System.out.print(num + " ");
}
}
Python Implementation
arr = [0, 2, 1, 2, 0]
arr.sort()
print(arr)
JavaScript Implementation
let arr = [0, 2, 1, 2, 0];
arr.sort((a, b) => a - b);
console.log(arr);
Output (All Languages)
0 0 1 2 2
Approach 2: Counting Method
Idea
Since the array contains only 0, 1, and 2, count how many times each appears and overwrite the array.
Algorithm
- Count number of 0s, 1s, and 2s
- Fill the array with:
- All 0s
- Then 1s
- Then 2s
Time & Space Complexity
- Time: O(n)
- Space: O(1)
Implementation
C
#include
int main() {
int arr[] = {0, 2, 1, 2, 0};
int n = 5;
int count0 = 0, count1 = 0, count2 = 0;
for(int i = 0; i < n; i++) {
if(arr[i] == 0) count0++;
else if(arr[i] == 1) count1++;
else count2++;
}
int index = 0;
while(count0--) arr[index++] = 0;
while(count1--) arr[index++] = 1;
while(count2--) arr[index++] = 2;
for(int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {0, 2, 1, 2, 0};
int n = 5;
int c0 = 0, c1 = 0, c2 = 0;
for(int i = 0; i < n; i++) {
if(arr[i] == 0) c0++;
else if(arr[i] == 1) c1++;
else c2++;
}
int idx = 0;
while(c0--) arr[idx++] = 0;
while(c1--) arr[idx++] = 1;
while(c2--) arr[idx++] = 2;
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Java
public class Sort012 {
public static void main(String[] args) {
int[] arr = {0, 2, 1, 2, 0};
int c0 = 0, c1 = 0, c2 = 0;
for(int num : arr) {
if(num == 0) c0++;
else if(num == 1) c1++;
else c2++;
}
int index = 0;
while(c0-- > 0) arr[index++] = 0;
while(c1-- > 0) arr[index++] = 1;
while(c2-- > 0) arr[index++] = 2;
for(int num : arr)
System.out.print(num + " ");
}
}
Python
arr = [0, 2, 1, 2, 0]
count0 = arr.count(0)
count1 = arr.count(1)
count2 = arr.count(2)
arr[:] = [0]*count0 + [1]*count1 + [2]*count2
print(arr)
JavaScript
let arr = [0, 2, 1, 2, 0];
let c0 = 0, c1 = 0, c2 = 0;
for (let num of arr) {
if (num === 0) c0++;
else if (num === 1) c1++;
else c2++;
}
let index = 0;
while (c0--) arr[index++] = 0;
while (c1--) arr[index++] = 1;
while (c2--) arr[index++] = 2;
console.log(arr);
Approach 3: Dutch National Flag Algorithm (Optimal)
Idea
Use three pointers:
- low → boundary for 0s
- mid → current element
- high → boundary for 2s
Algorithm
- Initialize low = 0, mid = 0, high = n - 1
- Traverse while mid <= high
- If arr[mid] == 0 → swap with low
- If arr[mid] == 1 → move mid
- If arr[mid] == 2 → swap with high
Time & Space Complexity
- Time: O(n)
- Space: O(1)
Implementation
C
#include
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int main() {
int arr[] = {0, 2, 1, 2, 0};
int n = 5;
int low = 0, mid = 0, high = n - 1;
while(mid <= high) {
if(arr[mid] == 0) {
swap(&arr[low], &arr[mid]);
low++; mid++;
}
else if(arr[mid] == 1) {
mid++;
}
else {
swap(&arr[mid], &arr[high]);
high--;
}
}
for(int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {0, 2, 1, 2, 0};
int n = 5;
int low = 0, mid = 0, high = n - 1;
while(mid <= high) {
if(arr[mid] == 0)
swap(arr[low++], arr[mid++]);
else if(arr[mid] == 1)
mid++;
else
swap(arr[mid], arr[high--]);
}
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Java
public class DutchFlag {
public static void main(String[] args) {
int[] arr = {0, 2, 1, 2, 0};
int low = 0, mid = 0, high = arr.length - 1;
while(mid <= high) {
if(arr[mid] == 0) {
int temp = arr[low];
arr[low++] = arr[mid];
arr[mid++] = temp;
} else if(arr[mid] == 1) {
mid++;
} else {
int temp = arr[mid];
arr[mid] = arr[high];
arr[high--] = temp;
}
}
for(int num : arr)
System.out.print(num + " ");
}
}
Python
arr = [0, 2, 1, 2, 0]
low = mid = 0
high = len(arr) - 1
while mid <= high:
if arr[mid] == 0:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
elif arr[mid] == 1:
mid += 1
else:
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
print(arr)
JavaScript
let arr = [0, 2, 1, 2, 0];
let low = 0, mid = 0, high = arr.length - 1;
while (mid <= high) {
if (arr[mid] === 0) {
[arr[low], arr[mid]] = [arr[mid], arr[low]];
low++; mid++;
} else if (arr[mid] === 1) {
mid++;
} else {
[arr[mid], arr[high]] = [arr[high], arr[mid]];
high--;
}
}
console.log(arr);
Dry Run (Dutch National Flag)
Initial: [0, 2, 1, 2, 0]
low=0 mid=0 high=4
Step 1: 0 → swap with low
[0, 2, 1, 2, 0]
Step 2: 2 → swap with high
[0, 0, 1, 2, 2]
Final: [0, 0, 1, 2, 2]
Summary
- Brute force works but inefficient
- Counting is simple and effective
- Dutch National Flag is optimal and interview-preferred
- Achieves sorting in one pass and constant space
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
