Given an array consisting of 0s, 1s, and 2s. Write code to sort an array of 0s, 1s, and 2s without using an extra space or a sorting algorithm.
OR
Given an array of size n containing only 0s, 1s, and 2s. Write a code to sort the array in ascending order.
For example:
Input : {0, 1, 1, 0, 1, 2, 0, 1, 2}
Output : {0, 0, 0, 1, 1, 1, 1, 2, 2}
In this example, the input array only consists of 0s, 1s, and 2s in an unsorted order.
In the output array, all the 0s, 1s and 2s are in sorted order.
The easiest version of this problem is to segregate 0s and 1s in an array and Move all zeros to end of array. This problem is also known as the Dutch national flag problem.
In this tutorial, I am going to discuss multiple approaches and their time and space complexities to solve this problem. Also, We’ll write the java code for all the approaches.
Also, at the end of this tutorial, I have shared the link to the video tutorial.
How to Sort an Array of 0s, 1s and 2s?
Let’s start with the simplest approach. The simplest solution is to sort an array. Once the array is sorted the number (0s, 1s, 2s) are arranged in sorted order.
|
1 2 3 4 5 6 |
//Sort 0s, 1s and 2s with sorting class Solution { public void sortColors(int[] nums) { Arrays.sort(nums); } } |
The time complexity of sorting an array is O(nlogn).
If you are not familiar with the sorting algorithm then check different sorting algorithms and their time complexities
Our problem is already solved. As per the problem statement, we have to arrange the 0s, 1s, and 2s in sorted order which we have done through sorting.
Can we further improve the time complexity of our solution? Yes, we can solve this problem in O(n) time complexity.
Sort an Array of 0s, 1s, 2s using Simple Counting – Java Code
The idea here is to count the number of zero and one present in an array. Once we know the count of zero and one we can easily find the count of two by subtracting the count of zero and one with an array length.
Now, we know the count of zero, one, and two present in an array. To arrange the 0s, 1s, and 2s in ascending order, we need to first put 0s than 1s, and after that 2s in an array.
The time complexity of this approach is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
/* Sort an array of zero, one and two using simple counting */ public class SortZeroOneTwo { public static void sort(int[] arr) { int zeroCount = 0; int oneCount = 0; /* Traverse an array and count number of zero and one present in an array. */ for (int i = 0; i < arr.length; i++) { /* If value is zero, increment the value of zeroCount variable. */ if (arr[i] == 0) zeroCount++; /* If value is one, increment the value of oneCount variable. */ if (arr[i] == 1) oneCount++; } //Put the zero's first in an array for (int i = 0; i < zeroCount; i++) { arr[i] = 0; } //After zero, put 1's in an array for (int i = zeroCount; i < (zeroCount + oneCount); i++) { arr[i] = 1; } //Rest put 2's in an array for (int i = (zeroCount + oneCount); i < arr.length; i++) { arr[i] = 2; } } public static void main(String[] args) { int[] arr = { 0, 1, 1, 0, 1, 2, 0, 1, 2 }; //Call sort method to sort an array sort(arr); //Traverse an array and print the sorted result for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } } |
Sort a linked list of 0s, 1s and 2s
Sort an Array of 0s, 1s, and 2s (In-place sorting)
The algorithm we are going to use in this example is also known as the Dutch national flag algorithm or three-way partitioning. The idea here is to sort an array of 0s, 1s, 2s in a single traversal without using extra space or a sorting algorithm.
Here are the following steps of this algorithm.
i) Declare three variables start=0, mid=0, high= n-1 where n is the length of an array.
ii) Run a loop until mid<=high and consider three cases on the basis of the value of array [mid].
- If the value array[mid] is 0.
Swap (array [start], array [mid])
Increment low
Increment mid
Break statement
- If the value of array[mid] is 1. Keep as it is since 1’s should be at the middle of a sorted array.
Increment mid
Break statement
- If array[mid] is 2.
Swap (array [mid], array [high])
Decrement high
Break statement
The time complexity of this approach is O(n) without using any extra space.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
/* Sort an array of zeros, ones, and twos without using extra space. */ public class SortZeroOneTwo { public static void sort(int[] arr) { int start = 0; int mid = 0; int high = arr.length - 1; while (mid <= high) { switch (arr[mid]) { case 0: { swap(arr, start, mid); start++; mid++; break; } case 1: mid++; break; case 2: { swap(arr, mid, high); high--; break; } } } } private static void swap(int[] arr, int start, int end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; } public static void main(String[] args) { int[] arr = { 0, 1, 1, 0, 1, 2, 0, 1, 2 }; sort(arr); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } } |
Sort an Array of 0s, 1s and 2s – Video Tutorial
In this tutorial, I have explained how we can segregate an array of 0s, 1s, and 2s using simple counting. Count the number of 0s, 1s, and 2s present in an array and then put them in sorted order.
