Be the first user to complete this post

  • 0
 Add to List
Beginner

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

Objec­tive:  Given an array that 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 the number of 0’s in the array. Say it's count.
  • Now in the array, put 0 in indexes from 0 to count – 1.
  • In the rest of the array put 1.

Time Complexity: O(n)

Output:

Output: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

Approach: Swapping Indexes

  • Use two indexes, left and right.
  • Put the left index at the start of the array and the 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)

Output:

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

Related Problems: