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