Separate 0’s and 1’s in a given array
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:
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]