Difficulty: Medium, Asked-in: Google, Facebook, Microsoft, Amazon, Paytm, Morgan Stanley, Hike, Walmart, Adobe, SAP Labs, Qualcomm
Key takeaway
Given an array X[] consisting of 0s, 1s, and 2s, write a program to sort the array of 0’s, 1’s, and 2’s in ascending order.
Input: X[] = [0, 2, 1, 0, 1, 2, 1, 0], Output: X[] = [0, 0, 0, 1, 1, 1, 2, 2]
Input: X[]= [0, 1, 1, 0, 1, 2, 1, 2, 0, 0], Output: X[] = [0, 0, 0, 0, 1, 1, 1, 1, 2, 2]
Input: X[] = [2, 1, 0], Output: X[] = [0, 1, 2]
The basic idea that comes to mind is to simply count the number of 0’s, 1’s, and 2’s. Then, place all 0’s at the beginning of the array followed by 1’s and 2's.
We declare three variables countZero, countOne, countTwo to store the frequency of 0’s, 1’s, and 2’s in the array.
int countZero = 0, countOne = 0, countTwo = 0
Now we traverse through the array to count the frequency of 0’s, 1’s, and 2's.
for (int i = 0; i < n; i = i + 1)
{
if (X[i] == 0) countZero = countZero + 1
if (X[i] == 1) countOne = countOne + 1
if (X[i] == 2) countTwo = countTwo + 1
}
void sort_0_1_2(int X[], int n)
{
int countZero = 0, countOne = 0, countTwo = 0;
for (int i = 0; i < n; i = i + 1)
{
if (X[i] == 0) countZero = countZero + 1;
if (X[i] == 1) countOne = countOne + 1;
if (X[i] == 2) countTwo = countTwo + 1;
}
int i = 0;
while (countZero != 0)
{
X[i] = 0;
i = i + 1;
countZero = countZero - 1;
}
while (countOne != 0)
{
X[i] = 1;
i = i + 1;
countOne = countOne - 1;
}
while (countTwo != 0)
{
X[i] = 2;
i = i + 1;
countTwo = countTwo - 1;
}
}
def sort_0_1_2(X, n):
count_zero = 0
count_one = 0
count_two = 0
for i in range(n):
if X[i] == 0:
count_zero = count_zero + 1
elif X[i] == 1:
count_one = count_one + 1
elif X[i] == 2:
count_two = count_two + 1
i = 0
while count_zero > 0:
X[i] = 0
i = i + 1
count_zero = count_zero - 1
while count_one > 0:
X[i] = 1
i = i + 1
count_one = count_one - 1
while count_two > 0:
X[i] = 2
i = i + 1
count_two = count_two - 1
Time complexity = Time complexity of counting 0’s, 1’s, and 2’s + Time complexity of placing 0’s, 1’s, and 2’s in the sorted order = O(n) + O(n) = O(n). As we are using constant extra space, so space complexity = O(1).
The critical question is: can we solve the problem in a single traversal of the array? We have only three unique elements in the input, so can we use an idea similar to the partition process of the quicksort to place the elements at their correct position in the sorted output? Let's think!
We can solve the problem using a single scan by maintaining the correct order of 0’s, 1’s, and 2’s using variables. Actually, we have three types of elements to be placed in sorted order, so we divide the given array into four sections using three-pointers. Let us name these pointers as low, mid, and high.
We initialise three pointers low = 0, mid = 0 and high = n - 1.
Now we scan the array using the mid pointer. In other words, we run a loop until mid <= high:
void sort_0_1_2(int X[], int n)
{
int low = 0, mid = 0, high = n - 1;
while (mid <= high)
{
if (X[mid] == 0)
{
swap(X[low], X[mid]);
low = low + 1;
mid = mid + 1;
}
else if (X[mid] == 1)
{
mid = mid + 1;
}
else if (X[mid] == 2)
{
swap(X[mid], X[high]);
high = high - 1;
}
}
}
def sort_0_1_2(X, n):
low = 0
mid = 0
high = n - 1
while mid <= high:
if X[mid] == 0:
X[low], X[mid] = X[mid], X[low]
low = low + 1
mid = mid + 1
elif X[mid] == 1:
mid = mid + 1
elif X[mid] == 2:
X[mid], X[high] = X[high], X[mid]
high = high - 1
In the worst case, we will be traversing and accessing each element of the array only once. Time complexity = O(n). Space complexity = O(1), As we are using a constant number of variables.
Please write in the message below if you find any errors or you want to share more insights. Enjoy learning, Enjoy coding, Enjoy algorithms!