Problem Statement
Given an array nums consisting of only 0, 1, or 2. Sort the array in non-decreasing order. The sorting must be done in-place, without making a copy of the original array.
LeetCode:
Examples
Example 1:
Input: arr[] = {0, 1, 2, 1, 2, 0, 0}
Output: {0, 0, 0, 1, 1, 2, 2}Example 2:
Input: arr[] = {2, 0, 1}
Output: {0, 1, 2}Different Approaches
1️⃣ Brute Force Approach
One might initially consider using a traditional sorting algorithm like Quick Sort or Merge sort to solve this problem.
Code:
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
//Function to sort the array
void sortZeroOneTwo(vector<int>& nums) {
// Sort the vector using std::sort
sort(nums.begin(), nums.end());
}
};
int main() {
vector<int> nums = {2, 0, 1, 1, 0, 2};
//Create an instance of Solution class
Solution sol;
sol.sortZeroOneTwo(nums);
//print the array elements
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}Complexity Analysis:
- Time Complexity:
O(NxlogN), whereNis the size of the array. As the optimal sorting takeO(N * logN)time. - Space Complexity:
O(1)no extra space is used to solve the problem.
2️⃣ Better Approach
Sorting an array containing only three distinct values -0s, 1s, and 2s - can be efficiently achieved by utilizing the frequency count of each value. This approach leverages the simplicity of counting occurrences and overwriting the array based on these counts.
Algorithm:
- Initialize three variables to maintain the count of 0s, 1s and 2s.
- Traverse the array once and increment the corresponding counting variables.
- Let's consider
count_0for the count of 0s,count_1for the count of 1s, andcount_2for the count of 2s.
- Let's consider
- In the second traversal of the array, overwrite the first
count_0indices/ positions in the array with0, the nextcount_1with1, and the remainingcount_2with2.
Code:
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to sort the array containing only 0s, 1s, and 2s
void sortZeroOneTwo(vector<int>& nums) {
int cnt0 = 0, cnt1 = 0, cnt2 = 0;
// Counting the number of 0s, 1s, and 2s in the array
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 0) cnt0++;
else if (nums[i] == 1) cnt1++;
else cnt2++;
}
/* Placing the elements in the
original array based on counts*/
//placing 0's
for (int i = 0; i < cnt0; i++) nums[i] = 0;
//placing 1's
for (int i = cnt0; i < cnt0 + cnt1; i++) nums[i] = 1;
//placing 2's
for (int i = cnt0 + cnt1; i < nums.size(); i++) nums[i] = 2;
}
};
int main() {
vector<int> nums = {0, 2, 1, 2, 0, 1};
// Create an instance of Solution class
Solution sol;
sol.sortZeroOneTwo(nums);
// Print the array elements after sorting
cout << "After sorting:" << endl;
for (int i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
cout << endl;
return 0;
}
Complexity Analysis:
Time Complexity: O(N) + O(N), where N = size of the array.
- This approach traverses the array twice - once for counting occurrences and once for overwriting.
- First
O(N)for counting the number of 0's, 1's, 2's - Second
O(N)for placing them correctly in the original array.
Space Complexity:O(1) as we are not using any extra space.
3️⃣ Optimal Approach (The Dutch National Flag Algorithm)
The Dutch National Flag Algorithm, proposed by Edsger W. Dijkstra, efficiently solves this problem in a single pass through the array. The algorithm operates on three pointers, namely low, mid, and height.
Algorithm:
- Initialize
lowto 0,midto 0, andhighton-1, where n is the size of the array. - Iterate through the array while
midis less than or equal tohigh. - If the element at the
midindex is 0, swap it with the element at thelowindex and increment bothlowandmid. - If the element at the
midindex is 1, simply incrementmid - If the element at the
midindex is 2, swap it with the element at thehighindex and decrementhigh - Repeat steps 2-5 until
midis greater thanhigh.
Dry Run:
Initialization:
+-----+-----+-----+-----+-----+-----+
nums = | 0 | 2 | 1 | 2 | 0 | 1 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
low high
midIterate while mid ≤ high
mid = 0
+-----+-----+-----+-----+-----+-----+
nums = | 0 | 2 | 1 | 2 | 0 | 1 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
low high
mid
Since nums[mid] == 0
Swap(nums[mid], nums[low])
Swap(0, 0)
mid++
low++
mid = 1
+-----+-----+-----+-----+-----+-----+
nums = | 0 | 2 | 1 | 2 | 0 | 1 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
low high
mid
Since nums[mid] == 2
Swap(nums[mid], high])
Swap(2, 1)
high--mid = 1
+-----+-----+-----+-----+-----+-----+
nums = | 0 | 1 | 1 | 2 | 0 | 2 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
low high
mid
Since nums[mid] == 1
mid++mid = 2
+-----+-----+-----+-----+-----+-----+
nums = | 0 | 1 | 1 | 2 | 0 | 2 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
low mid high
Since nums[mid] == 1
mid++mid = 3
+-----+-----+-----+-----+-----+-----+
nums = | 0 | 1 | 1 | 2 | 0 | 2 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
low mid high
Since nums[mid] == 2
Swap(2, 0)
high--mid = 3
+-----+-----+-----+-----+-----+-----+
nums = | 0 | 1 | 1 | 0 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
low mid
high
Since nums[mid] == 0
Swap(nums[low], nums[mid])
low++
mid++mid = 4, Loop Termination
+-----+-----+-----+-----+-----+-----+
nums = | 0 | 0 | 1 | 1 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
low high mid
Since mid crosses the high
So, we are done and terminate the loop.Code:
#include <iostream>
#include <vector>
void sort012(std::vector<int>& nums) {
int low = 0;
int mid = 0;
int high = nums.size() - 1;
while (mid <= high) {
switch (nums[mid]) {
case 0:
std::swap(nums[low++], nums[mid++]);
break;
case 1:
mid++;
break;
case 2:
std::swap(nums[mid], nums[high--]);
break;
}
}
}
int main() {
std::vector<int> arr = {2, 1, 0, 1, 2, 0, 1, 0, 2};
sort012(arr);
std::cout << "Sorted array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
// Output
Sorted array: 0 0 0 1 1 1 2 2 2 Another way:
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
// `low` for next position of 0
// `middle` is current element being examined
// `high` for next position of 2
int low = 0, middle = 0, high = n - 1;
// Process until middle crosses high
while (middle <= high) {
if (nums[middle] == 0) {
// Swap current element with low position and move both forward
swap(nums[middle], nums[low]);
low++;
middle++;
}
else if (nums[middle] == 2) {
// Swap current element with high position and move high backward
swap(nums[middle], nums[high]);
high--;
// Do not increment middle here as the swapped element needs to be checked
}
else {
// If it's 1, just move middle ahead
middle++;
}
}
}
};
Complexity Analysis:
- Time Complexity:
O(n) - Space Complexity:
O(1)