Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach-1
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Approach-2
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is Dutch National Flag Problem ? 
4.2.
What would be the time complexity if we used built-in sort function ?
4.3.
What is the significance of mid index in the first approach?
5.
Conclusion
Last Updated: May 6, 2024

Sort an Array of 0s,1s and 2s

Author Ankit kumar
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This blog will discuss the approach to sorting an array containing 0s,1s, and 2s. Before jumping on the approach to the problem, let us first understand the problem.

Problem Statement

Given an array of 0s,1s and 2s, we have to sort the array in ascending order, i.e., 0s come first, then 1s, and finally 2s. Note that the array does not contain any other elements than these three.

Sample Example

Input : [1,0,0,2,1,0,1]

 

Output : [0,0,0,1,1,1,2]

Approach-1

This problem is a variation of the famous problem, Dutch National Flag Problem. In this approach, the array is divided into four sections,

  1. arr[0...to…LOW-1] (Zero)
  2. arr[LOW…to…MID-1] (One)
  3. arr[MID…to…HIGH] (unknown)
  4. arr[HIGH+1…to…N-1] (two)

 

If the ith element is 0, then swap it with low range, which in turn reduces the unknown range. Similarly, if the ith element is 1, then simply reduce the unknown range, and finally, if the ith element is 2, then swap it with the element in the high range.

Steps of Algorithm

Step 1: Maintain three indices as low = 0,mid = 0 and high = n-1

Step 2: Traverse the array from start to end while mid is less than equals to high

Step 3: If the element at index mid is 0, then swap it with the element at index low. Simultaneously increment the index of low and mid-index.

Step 4: If the element at index mid is 1,then shrink the unknown range, i.e , increment the mid index(mid = mid  + 1).

Step 5: If the element at index mid is 2, then swap it with the element at index high. simultaneously decrease the index of high(high = high - 1).

Step 6: Print the array.

Implementation in C++

// c++ program to sort the array of 0,1,2 in one go.
#include <bits/stdc++.h>
using namespace std;
// function to sort the array of 0,1,2.
void sortArr(int arr[], int n)
{
    int low = 0, mid = 0, high = n - 1;
    while (mid <= high)
    {
        // if the middle element is 0.
        if (arr[mid] == 0)
        {
            swap(arr[mid++], arr[low++]);
        }
        // if the middle element is 1.
        else if (arr[mid] == 1)
        {
            mid++;
        }
        // if the middle element is 2.
        else
        {
            swap(arr[mid], arr[high--]);
        }
    }
}
// main function.
int main()
{
    // input array arr.
    int arr[] = {1, 0, 0, 2, 1, 0, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    // call of sort function
    sortArr(arr, n);
    // printing the resultant array after sorting.
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
}

 

Output :

 [0,0,0,1,1,1,2]

 

Complexity Analysis

Time Complexity : O(n)

Since only one traversal is performed in total which costs O(n) time ,other operations are of constant time complexity, therefore total time complexity would be of the order O(n).

Space Complexity : O(1)

As no extra space is required apart from the given space, therefore the space complexity would be of the order O(1).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach-2

In this approach, we used to count the number of 0s,1s, and 2s and then store all the 0s first, then 1s, and finally 2s. This is a simple, intuitive approach.

Steps of Algorithm

Step 1: Maintain three counter count0 = 0,count1 = 0 and count2 = 0 respectively for 0s,1s and 2s.

Step 2: Traverse the array and increase the counters according to the elements encountered.

Step 3: Now again, traverse the array and replace the first count0 elements with 0, next count1 elements with 1, and finally next count2 elements with 2.

Implementation in C++

//c++ program to sort the array- brute force
#include <bits/stdc++.h>
using namespace std;
//function to sort the array of 0,1,2
void sortArr(int arr[], int n){
	//count variables to count the number of 0,1 and 2 respectively.
	int count0 = 0,count1 = 0,count2 = 0;
	//iterator
	int i;
	for(i = 0;i < n;i++){
		//if the element found is 0
		if(arr[i] == 0)
			Count0++;
		//if the element found is 1
		else if(arr[i] == 1)
			Count1++;
		//if the element found is 2
		else
			count2++;
	}
	i = 0;
	//storing all the 0s in the beginning
	while(count0--){
		arr[i++] = 0;
	}

	//then all the 1s in the middle
	while(count1--){
		arr[i++] = 1;
	}

	//and finally 2s in the last
	while(count2--){
		arr[i++] = 2;
	}
}
//main function
int main(){
	//input array arr
	int arr[] = {1,0,0,2,1,0,1};
	int n = sizeof(arr)/sizeof(arr[0]);
	//call of sort function
	sortArr(arr,n);
	//printing the resultant array
	for(int i = 0 ; i<n; i++)
		cout<<arr[i]<<" ";
}

 

Output : 

[0,0,0,1,1,1,2]

 

Complexity Analysis

Time Complexity : O(n)

Since only one traversal is performed in total which costs O(n) time ,other operations are of constant time complexity, therefore total time complexity would be of the order O(n).

Space Complexity : O(1)

As no extra space is required apart from the given space, therefore the space complexity would be of the order O(1).

Also see, Euclid GCD Algorithm

Frequently Asked Questions

What is Dutch National Flag Problem ? 

Given balls of three colors arranged randomly in a line. The aim is to arrange them such that all balls of the same color get together and their collective color groups get in the correct order.

What would be the time complexity if we used built-in sort function ?

If we used the built-in sort function, the time complexity would be of the order of nlog(n) since it does not utilize the information that this array is only contained three elements.

What is the significance of mid index in the first approach?

In the first approach, the mid-index acts as an iterator as well as a barrier between the low range and mid-range. It is mid-index that iterates over the whole array.

Conclusion

This article discusses the different approaches to sorting the array containing 0s,1s, and 2s, starting with the approach which is similar to the approach in the Dutch national flag problem and then an intuitive approach that simply maintains the count and finally stores it in the correct place.

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Car Pooling
Next article
Minimum coverage by heaters
Live masterclass