How to segregate 0s and 1s in C++

Suppose we’re working on a project that deals with binary data where 0 represents one state and 1 represents another. For example, in computer science, 0s and 1s usually represent off/on, false/true, or similar binary states.

Consider another scenario where we have an array of binary numbers. We need to organize them in a way that all the 0s come before the 1s. This situation can arise when processing binary data in various applications, such as image processing, sorting binary data, signal processing, and data compression.

Let's come to the implementation of segregating 0s and 1s in C++.

Implementation of segregating 0s and 1s

Let’s examine these approaches to determine the best one based on time and space complexity.

Naive approach

To solve the segregate 0s and 1s problem, we can use two separate arrays. We can iterate through the input array and maintain two separate arrays, one for 0s and the other for 1s. After iterating through the input array, we can concatenate the two arrays to get the segregated array. However, this approach requires extra space for the two arrays, which is not optimal. Therefore, we prefer to use an optimized approach to save extra space.

Optimized approach using two pointers

To solve this problem, we use an array and two pointers, left and right. The left pointer traverses from the start toward the end until it points to 1. The right pointer moves from the end toward the start until it points to 0. Swapping is performed in each iteration based on whether the left side has a 0 and the right side has a 1.

Let’s examine the complete process of segregating 0s and 1s below:

#include <iostream>
using namespace std;
void segregateZerosAndOnes(int arr[], int size) {
    int l = 0;
    int r = size - 1;
    while (l < r) {
        // Increment l pointer while there are 0s at the beginning
        while (arr[l] == 0)
            l++;
        // Decrement right pointer while there are 1s at the end
        while (arr[r] == 1)
            r--;
        // Swap 0 at the left pointer with 1 at the right pointer
        if (l < r) {
            swap(arr[l], arr[r]);
            l++;
            r--;
        }
    }
}
int main() {
    int arr[] = {0, 1, 0, 1, 1, 0, 0, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    segregateZerosAndOnes(arr, size);
    cout << "Segregated Array: ";
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    return 0;
}

Code explanation

Here’s the explanation of the above code.

Lines 5–6: Set l to the start of the array and r to the end of the array.
Line 8: while loop will continue until the l is less than the r.
- Lines 10–11: Move the l pointer to the right until it points to a 1 (skipping 0s).
- Lines 14–15: Move the r pointer to the left until it points to a 0 (skipping 1s)
- Lines 18–22: If l is still less than r, swap the values at the l and r pointers. This puts a 0 on the left side and a 1 on the right side.
Line 27: array is initialized with 0s and 1s.
Line 30: Call the function segregateZerosAndOnes() and pass the array arr to rearrange 0s and 1s.
Lines 33–34: Print the segregated array arr on the console.

Time complexity

The algorithm iterates through the array once with two pointers, l and r, performing constant-time operations at each step, resulting in a time complexity of $O(n)$ .

Space complexity

The algorithm uses only a constant amount of extra space for both pointers, leading to a space complexity of $O(1)$ .

Ready to master C++?

Our Learn C++ course will help you build practical skills, from basic loops to complex program structures. Join now and start coding your way to success!

Free Resources