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

by

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:


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:


Output:

[0, 0, 0, 1, 1, 1, 1, 1]

Related Posts: