PROBLEM DESCRIPTION
Given an array of size N containing only 0s, 1s, and 2s; sort the array in ascending order.
SOLUTION
This is a very interesting question and the optimal solution is not easy to come up with. We are supposed to solve this problem in linear time. So we cannot use any of the sorting algorithms like Merge Sort etc.
Let us first look into the simpler solution which uses two iterations.
APPROACH 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public static void sort012(int a[], int n)
{
// Create an array to store the frequency of 0s, 1s, and 2s
int[] freq = new int[3];
// Store frequency of 0, 1, and 2 in their corresponding index in the frequency array
for(int i=0; i<n; i++)
freq[a[i]]++;
// Update the original array with the sorted order based on the frequency of 0s, 1s, and 2s
// Update 0s based on their frequency
for(int i=0; i<freq[0]; i++)
a[i] = 0;
// Update 1s based on their frequency
for(int i=freq[0]; i<freq[0]+freq[1]; i++)
a[i] = 1;
// Update 2s based on their frequency
for(int i=freq[0]+freq[1]; i<freq[0]+freq[1]+freq[2]; i++)
a[i] = 2;
}
}
APPROACH 2 - OPTIMAL
takeUForward - Good Explanation
The idea is to do the following:
- We need to use a
lowpointer before which all the numbers should be 0. - We need to use a
highpointer after which all the numbers should be 2. - We need to use a
midpointer which will help in checking the elements one by one and putting them in the right position
If we can make sure that all the numbers before low are 0, and all numbers after high are 2, then we have already sorted these two parts. So, we just need to sort the remaining unsorted path from [mid, high-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution
{
public static void sort012(int a[], int n)
{
int low = 0; // all numbers before low will be 0
int mid = 0; // help with iteration
int high = n-1; // all numbers after high will be 2
// high will continue to decrease whenever we get a 2
// mid will continue to increase during iterations
// we will continue doing so until mid<=high
while(mid <= high){
// if element at mid is 0
// we need to bring it to the front, so swap elements at low and mid
// now, low can move one step forward
// to check the next element, we move mid as well
if(a[mid] == 0){
swap(a, low, mid);
mid++;
low++;
// this one is important
// if the current element at mid is 2
// we need to move it to the right side
// we can swap the elements at mid and high
// then, we can definitely reduce the value of high (since we want all numbers on right of high to be 2)
// but we might have brought in a different number which can be 0/1/2 from index high
// so we should not really increase the mid pointer this time
// it will get handled in the next iteration
}else if(a[mid] == 2){
swap(a, high, mid);
high--;
// if the element at mid is 1, nothing to do actually since all the 1s will eventually get sorted
}else{
mid++;
}
}
}
public static void swap(int[] a, int i, int j){
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}