How to Segregate 0s and 1s in an Array.
Given an array of 0s and 1s in a random order. We have to write a code to segregate 0s on the left side and 1s on the right side of the array.
Basically, we have to sort an array of 0s and 1s.
For example –
Input array = [0, 1, 0, 1, 0, 0, 1]
Output array = [0, 0, 0, 0, 1, 1, 1]
In an input array 0s and 1s are in an unsorted order. The output is the sorted order of 0s and 1s.
How to sort an array of 0s and 1s in a Single traversal
This programming problem is similar to the problem of move all zeroes to end of array. In this tutorial, I am going to discuss multiple approaches and it’s java code to solve this problem.
Sort an array of 0s, 1s and 2s.
Let’s start with the easiest approach first. What’s the easiest approach we can use to solve this problem. The simplest approach is to sort an array of 0s and 1s. Once the array is sorted all zeroes moves on the left side and 1s on the right side.
The time complexity of sorting an array is O(nlogn).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
//Separate 0s and 1s in array using Sorting public class SegregateZeroOne { public static int[] separateZeroOne(int[] arr) { //Sort an array Arrays.sort(arr); return arr; } public static void main(String[] args) { int[] arr = {1, 0 ,1, 0, 0, 1}; int[] result = separateZeroOne(arr); for(int i = 0; i < result.length; i++) { System.out.print(result[i] + " "); } } } |
How we can improve our solution to solve this problem in O(n) time complexity?
Algorithm to Segregate 0s and 1s in an Array in Single Traversal
To solve this problem in a single traversal. Traverse an array and put the 0s at the beginning. Once we put all the zeroes at the beginning of an array we are only left with 1s. Then put 1s in an array.
The time complexity of this approach is O(n) and it’s space complexity is O(1).
Segregate 0s and 1s in an Array – Java Code
In this coding example, Let’s implement the algorithm which we discussed above.
|
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 |
/** Java Program to sort an array of 0s and 1s in one traversal. */ public class SegregateZeroOne { public static int[] separateZeroOne(int[] arr) { int j = 0; // Traverse an array for (int i = 0; i < arr.length; i++) { // If value at index is equal to 0 if (arr[i] == 0) { [j++] = arr[i]; } } // We have already moved zero, Now the remaining values is 1 while (j < arr.length) { arr[j++] = 1; } return arr; } public static void main(String[] args) { int[] arr = {1, 0, 1, 0, 0, 1}; int[] result = separateZeroOne(arr); for (int i = 0; i < result.length; i++) { System.out.print(result[i] + " "); } } } |
In this video tutorial, I have explained how to sort an array of 0s and 1s in a single traversal.
