Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 17 Nov, 2020

Easy

```
Input: 'arr' = [2, 2, 2, 2, 0, 0, 1, 0]
Output: Final 'arr' = [0, 0, 0, 1, 2, 2, 2, 2]
Explanation: The array is sorted in increasing order.
```

```
The first line contains a positive integer ‘n’, which represents the length of the array/list.
The second line of each test case contains ‘n’ single space-separated integers representing the elements of the array/list.
```

```
The output will print ‘n’ single space-separated integers of the sorted array/list.
```

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

Simply, we will sort the array.

A two-pass algorithm can easily solve the problem. We will count the number of 0s, 1s and 2s in the array/list.

Then, we will overwrite the array with the total number of 0s, followed by 1s and 2s, respectively.

We can sort the array in one-pass by maintaining three positional pointers ‘zeroPos’, ‘onePos’ and ‘twoPos’ initialised to 0, 0 and n - 1, respectively.

Here, ‘zeroPos’ represents the first 1 after all 0s, ‘onePos’ represents the current element, and ‘twoPos’ represents the last unexplored element before all 2s.

Now, we iterate through ARR with ‘onePos’-

- If we encounter a 0.
- We will swap arr[zeroPos] and arr[onePos].
- This is because ‘zeroPos’ represents the first 1 after all 0s and we have to ensure that all 0s must come before 1.
- Then increment ‘zeroPos’ and ‘onePos’ by 1.

- Else, If we encounter a 1.
- We will simply increment ‘onePos’ by 1.

- Else, If we encounter a 2.
- We will swap arr[onePos] and arr[twoPos].
- This is because ‘twoPos’ represents the last unexplored element before all 2s and we have to ensure that all 2s must come after 1.
- Then decrement ‘twoPos’ by 1.

Similar problems