menu

### Sort an array of 0s, 1s and 2s

**Problem Statement:** Given an array consisting of only 0s, 1s, and 2s. Write a program to in-place sort the array without using inbuilt sort functions. ( Expected: Single pass-O(N) and constant space)

##
Examples

Input:nums = [2,0,2,1,1,0]Output: [0,0,1,1,2,2]Input:nums = [2,0,1]Output:[0,1,2]Input:nums = [0]Output:[0]

### Solutions

##
Brute Force Approach

##### Algorithm

While sorting may not be the anticipated solution, it remains a viable approach in this scenario. Given the array comprises solely the integers 0, 1, and 2, sorting would effectively arrange the elements in ascending order.

##### Time and Space Complexity

Time Complexity: O(N*logN)

Space Complexity: O(1)

##
Better Approach

##### Algorithm

Maintaining a count of values.

##### Intuition

Since there are only 3 different numbers in the array—0, 1, and 2—it’s easy to count how many of each are there. We can then change the array based on how many times each number appears.

##### Approach

- Use three variables to keep track of how many times 0, 1, and 2 appear.
- Go through the array once and add to the count for each respective number.
- During the second scan through the array, we’ll replace the first ‘a’ indices or positions in the array with ‘0’, the subsequent ‘b’ with ‘1’, and the rest of the ‘c’ with ‘2’.

##### Code

` ````
```def sortArray(arr):
count_0 = 0
count_1 = 0
count_2 = 0
for num in arr:
if num == 0:
count_0 += 1
elif num == 1:
count_1 += 1
else:
count_2 += 1
for i in range(count_0):
arr[i] = 0
for i in range(count_0, count_0 + count_1):
arr[i] = 1
for i in range(count_0 + count_1, len(arr)):
arr[i] = 2
n = 6
arr = [2, 0, 2, 1, 1, 0]
sortArray(arr)
print(arr)

##### Output

[0, 0, 1, 1, 2, 2]

##### Time and Space Complexity

__Time Complexity:__ O(N) + O(N). It takes O(N) time twice, where N is the size of the array. The first O(N) is for counting the occurrences of 0, 1, and 2, and the second O(N) is for correctly positioning them within the original array.

__Space Complexity:__ O(1) as we are not using any extra space.

##
Optimal Approach

##### Algorithm

This method involves using three pointers: low, mid, and high, along with three key rules:

- Elements from arr[0 to low-1] are all 0s. [Leftmost segment]
- Elements from arr[low to mid-1] are all 1s.
- Elements from arr[high+1 to n-1] are all 2s. [Rightmost segment], where n is the size of the array.

##### Short Video Explanation

For a better understanding of the algorithm, please watch the video by clicking on the button below.

##### Code

Refer the code below for better understanding.

` ````
```
def sortArray(arr):
low = 0
mid = 0
high = len(arr) - 1
while mid <= high:
if arr[mid] == 0:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
elif arr[mid] == 1:
mid += 1
else:
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
n = 6
arr = [2, 0, 2, 1, 1, 0]
sortArray(arr)
print(arr)

##### Output

[0, 0, 1, 1, 2, 2]

##### Time and Space Complexity

__Time Complexity:__ O(N), where N = size of the given array.

__Space Complexity:__ O(1) as we are not using any extra space.

WhatsApp

Facebook

Twitter

LinkedIn

Email

Perfect