Segregate 0s, 1s and 2s in an array (Sort an array of 0s, 1s and 2s)

Posted by N.K. Chauhan on Jan 03, 2022

An array A is given, A contains only 0s, 1s and 2s in random order. The task is to Segregate 0s on left side and 2s on right side of the array (sort the array) in O(n) time complexity.

Example 1: Segregate 0s and 1s in: {1, 0, 0}

Input: {1, 0, 0}
Output: {0,0,1}

Example 2: Segregate 0s and 1s in: {2, 0, 1, 0, 0, 1, 2, 1, 0}

Input: {2, 0, 1, 0, 0, 1, 2, 1, 0}
Output: {0,0,0,0,1,1,1,2,2}


Solutions

Method 1: Counting 0s,1s and 2s

We can solve this problem in O(n) time while traversing the array twice, once to count the occurrences of 0s, 1s and 2s and second time to fill the array with 0s, 1s and 2s based on respective count.

0,0,0,0,1,1,1,2,2
0,0,1

Complexity

We need to traverse the array twice and that is not dependent on length (n) of array, hence the time complexity of this solution is O(n) and space complexity is O(1).

Method 2: Dutch National Flag

In this approach we will use famous Dutch National Flag algorithm.

The idea is to divide the array in four parts such that; 1 to low-1 will have 0s, low to mid-1 will have 1s, mid to high-1 will have unsorted elements and high to n-1 will have 2s.

Start with low=0, mid=0 and high=n-1 and traverse the array until mid <= high.

1) If arr[mid] == 0, swap arr[low] with arr[mid] and increment low (low++) and mid (mid++)

2) Else, if arr[mid] == 1, increment mid (mid++)

3) Else, if arr[mid]==2, swap arr[mid] with arr[high] and decrement high (high--).

0,0,0,0,1,1,1,2,2
0,0,1

Complexity

The time complexity of this solution is O(n) and space complexity is O(1).

Related


Two Sum - return index of a pair of array elements with a given sum

Word Break Problem (Using HashMap and DP)

Program to print Union of two sorted arrays

Merge two sorted arrays in O(1) space

Print all Subsets (Power Set) of a given array

Count the number of inversions in an array - in O(n log n) time

Program to print Intersection of two sorted arrays

Longest substring without repeating characters

Rain water trapping problem - O(n) time & O(n) space

Print all possible permutations of an Array in O(1) space

Find a triplet in an array that sums to a given number