Objective: Given an array which contains only 0’s and 1’s. write an algorithm to separate 0’s and 1’s.
Example
int [] arrA = {1,0,1,0,1,1,0,0,0,0,1};
Output: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
Approach: Counting
- Count number of 0’s in the array. Say its count.
- Now in array, put 0 in indexes from 0 to count – 1.
- In rest of the array put 1.
Time Complexity: O(n)
Code:
| import java.util.Arrays; | |
| public class Separate0and1Counting { | |
| public static int[] arrange(int [] arrA){ | |
| //count number of 0's | |
| int countOs=0; | |
| int size = arrA.length; | |
| for (int i = 0; i <arrA.length ; i++) { | |
| if(arrA[i]==0) | |
| countOs++; | |
| } | |
| for (int i = 0; i <arrA.length ; i++) { | |
| if(countOs>0) { | |
| arrA[i] = 0; | |
| countOs—; | |
| } | |
| else | |
| arrA[i]=1; | |
| } | |
| return arrA; | |
| } | |
| public static void main(String[] args) { | |
| int [] arrA = {1,0,1,0,1,1,0,0,0,0,1}; | |
| System.out.println("Rearranging arrays using counting.."); | |
| arrA = arrange(arrA); | |
| System.out.println(Arrays.toString(arrA)); | |
| } | |
| } |
Output: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
Approach: Swapping Indexes
- Use two indexes, left and right.
- Put left index at the start of array and right at the end of the array.
- Increment left till 1 is not found.
- Decrement right till 0 is not found.
- Swap left and right elements
- Do it till left<right
Time Complexity: O(n)
Code:
| import java.util.Arrays; | |
| public class Separate0and1UsingIndex { | |
| public static int[] arrange(int [] arrA){ | |
| int left =0; | |
| int right = arrA.length–1; | |
| while(left<right){ | |
| if(arrA[left]==0) | |
| left++; | |
| else if(arrA[right]==1) | |
| right—; | |
| else{ | |
| //swap left and right elements | |
| arrA[left] = 0; | |
| arrA[right] = 1; | |
| left++; | |
| right—; | |
| } | |
| } | |
| return arrA; | |
| } | |
| public static void main(String[] args) { | |
| int [] arrA = {1,0,1,0,1,1,0,1}; | |
| System.out.println("Rearranging arrays using left and right indexes"); | |
| arrA = arrange(arrA); | |
| System.out.println(Arrays.toString(arrA)); | |
| } | |
| } |
Output:
[0, 0, 0, 1, 1, 1, 1, 1]