**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]