Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive:  Given an array which con­tains only 0’s and 1’s. write an algo­rithm to sep­a­rate 0’s and 1’s.

Exam­ple

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: Count­ing

  • Count num­ber 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 Com­plex­ity: O(n)

Code:

Out­put: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

Approach: Swap­ping Indexes

  • Use two indexes, left and right.
  • Put left index at the start of array and right at the end of the array.
  • Incre­ment left till 1 is not found.
  • Decre­ment right till 0 is not found.
  • Swap left and right elements
  • Do it till left<right

Time Com­plex­ity: O(n)

Code:


Output:

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

You may also like...