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

In this article, we aim to understand and solve the problem of sorting an array that contains 0, 1, and 2. This problem is also known as the Dutch National Flag problem. So in simple words, here we are given an unsorted array that will have 0, 1, and 2 and we just have to sort them and return the array.

Problem Description:

Given an array of N size, the array contains 0,1 and 2. Return the sorted array.

Example:

N = 6

Arr = [0,2,2,1,0,1]

Output:

Arr = [0,0,1,1,2,2]

Solution 1:

Explanation:

·       We create 3 variables to keep the count of 0, 1, and 2 in the array.

·       We then traverse the entire array and count the number of 0’s, 1’s, and 2’s present in the array and store them in their respective count variable.

·       Finally, according to the counts of 0, 1, and 2 we add 0, 1, and 2 in the array respectively.

Time Complexity: O(N)

Space Complexity: O(1)

Solution 2:

Explanation:

·       We create 3 variables low, mid, and high. The low and mid variables will be at the start and the high will be at the end.

·       So the idea is that if the mid element is 0, low and mid swap the elements and both go ahead by 1.

·       If the mid element is 1 then only mid goes ahead by 1.

·       If mid has 2 then it swaps with high and high is decremented by 1.

Time Complexity: O(N)

Space Complexity: O(1)