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)

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

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)

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
  1. Use three variables to keep track of how many times 0, 1, and 2 appear.
  2. Go through the array once and add to the count for each respective number.
  3. 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.

Algorithm

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

  1. Elements from arr[0 to low-1] are all 0s. [Leftmost segment]
  2. Elements from arr[low to mid-1] are all 1s.
  3. 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

Leave a Reply

Your email address will not be published. Required fields are marked *

Welcome to our diverse learning options!

Select the learning format that suits your preferences and schedule.