# Sort An Array of 0s, 1s and 2s

Posted: 17 Nov, 2020

Difficulty: Easy

#### You have been given an array/list ARR consisting of ‘N’ elements. Each element in the array is either 0, 1 or 2.

#### Now, your task is to sort this array/list in increasing order. For example, if ARR = [0, 2, 1, 1], then after sorting ARR must look like [0, 1, 1, 2].

##### Input Format:

```
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of each test case 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.
```

##### Output Format:

```
For each test case, the only line of output will print ‘N’ single space-separated integers of the sorted array/list.
Print the output of each test case in a separate line.
```

#### Note:

```
You are not required to print the expected output; it has already been taken care of. Just implement the function.
```

##### Constraints:

```
1 <= T <= 100
1 <= N <= 5000
0 <= ARR[i] <= 2
Time limit: 1 sec
```

Approach 1

Approach 2

Approach 3

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

# Game of 3

Posted: 11 Jul, 2021

Difficulty: Easy

# Lexicographic Permutation Rank

Posted: 13 Jul, 2021

Difficulty: Moderate

# Zero Pair Sum

Posted: 22 Jul, 2021

Difficulty: Moderate

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy

# Remove K Corner Elements

Posted: 31 Jul, 2021

Difficulty: Easy