Separate 0s and 1s - O(N) Single Iteration

Given an array of numbers consisting of only zeroes and ones, and we need to separate 0s and 1s. This problem can be solved in many ways like sorting and performing basic swapping but I learned a method to do all of this in a single iteration. So, let’s do this.

Example

Input: 1  0  1  0  0  1  0  1  1
Output: 0  0  0  0  1  1  1  1  1

Input: 0 1 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0
Output: 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1

Solution Approach

Method 1

Here, we have 0s and 1s. Basically, by separating them, they would be in ascending order. So, this can also be done by using any basic sorting technique like Bubble Sort or Quick Sort. However, the time complexities can vary a lot depending on the order of the array given, and the best or worst-case complexity.

Method 2 – Optimized O(N)

Separate 0s and 1s in an array, using two pointers.

First, we take two pointers – [always] and [asuwish]. Both of them start from the beginning but the [always] pointer keeps on moving irrespective of what we get 0 or 1 but the [asuwish] pointer stops once it encounters a 1 on its way and increments only when it encounters a zero.

And the swapping occurs when,

arr[asuwish] == 1 && arr[always] == 0

I think the logic is clear, if you’re still confused take a look at the code below and perform a small dry run using pen and paper and you’ll understand it easily.

Note: The name of pointer is just to memorize easily, you can change them asuwish

Program to Separate 0s and 1s

#include <iostream>
using namespace std;
int main()
{
    int arr[] = {0, 1, 1, 0, 0, 0, 1, 0};
    int asuwish, always, noe, temp;
    noe = sizeof(arr) / sizeof(arr[0]);

    for (asuwish = 0, always = 0; always < noe; always++)
    {
        if (arr[asuwish] == 1 && arr[always] == 0)
        {
            temp = arr[always];
            arr[always] = arr[asuwish];
            arr[asuwish] = temp;
        }
        if (arr[asuwish] == 0)
            asuwish++;
    }

    for (always = 0; always < noe; cout<<arr[always++]<<" ");
    return 0;
}

Working

Here’s what happens at each iteration

0,0,1,1,0,0,1,0
0,0,0,1,1,0,1,0
0,0,0,0,1,1,1,0
0,0,0,0,0,1,1,1

Conclusion

This post [Separate 0s and 1s] is a part of my #30DaysChallenge to write a blog post every day on what I learn daily, All the Best~ Abhiram Reddy.

Separate 0s and 1s – O(N) Single Iteration