Separate 0’s and 1’s in a given array

Objec­tive:  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.length1;
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]

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.