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).