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]
Solution Idea and Steps
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 update 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
}
Now, we again traverse the array and replace the first countZero places of the array as 0, next countOne places by 1, and last countTwo places by 2.
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
}
Solution Pseudocode
Solution Analysis
Time complexity = Time complexity of counting 0’s, 1’s, and 2’s + Time complexity of placing all 0’s, 1’s, and 2’s in the array = O(n) + O(n) = O(n). As we are using constant extra space, so space complexity = O(1).
Solution Idea
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, therefore, we divide the given array into four sections using three-pointers. Let us name these pointers as low, mid, and high.
Solution Steps
Run a loop until mid<=high
Solution Pseudocode
Time and space complexity analysis
In the worst case, we are 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.
Thanks to Navtosh Kumar for his contribution in creating the first draft. Please write comments if you find an error or you want to share more insights about the topic. Enjoy learning, Enjoy coding, Enjoy algorithms!
In recursive DFS traversals of a binary tree, we have three basic elements to traverse— root, left subtree, and right subtree. The traversal order depends on the order in which we process the root node. Here recursive code is simple and easy to visualize — only one function parameter and 3–4 lines of code. So critical question would be — How can we convert it into iterative code using stack? To simulate the recursive traversal into an iterative traversal, we need to understand the flow of recursive calls.
Have you ever thought of any such service that could make our life easier by allowing us to store data over the internet and simultaneously allow others to access the same data? If it is so, then this is the perfect blog for you. Here, in this blog, we'll be discussing the PasteBin System. Here, the aim is to design a highly scalable service that could allow users to paste various content (images, text, etc.) over the internet and allow others to access the pasted content. So let's look at the formal definition of PasteBin.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops and math. enjoy learning!