Sort Binary Array - C++ Solution

1. Introduction

Sorting a binary array in linear time and constant space is a problem that combines array manipulation with the constraints of time and space efficiency. This task is often used to test a programmer's ability to apply sorting algorithms in a constrained environment, focusing on in-place operations.

Problem

The objective is to sort a binary array (consisting only of 0s and 1s) such that all zeroes are positioned before all ones. The solution must be implemented in linear time (O(n)) and constant space, meaning it should modify the array in-place without using additional storage proportional to the array size.

2. Solution Steps

1. Maintain two pointers, one at the beginning (zeroIndex) and one at the end (oneIndex) of the array.

2. Iterate through the array while zeroIndex is less than oneIndex.

3. If the element at zeroIndex is 0, increment zeroIndex.

4. If the element at oneIndex is 1, decrement oneIndex.

5. If the element at zeroIndex is 1 and the element at oneIndex is 0, swap them.

6. Continue the process until zeroIndex is greater than or equal to oneIndex.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to sort a binary array in linear time and constant space
void sortBinaryArray(vector<int>& nums) {
    int zeroIndex = 0; // Pointer to track the position for 0s
    int oneIndex = nums.size() - 1; // Pointer to track the position for 1s

    while (zeroIndex < oneIndex) {
        if (nums[zeroIndex] == 0) {
            zeroIndex++; // Increment zeroIndex if current element is 0
        } else if (nums[oneIndex] == 1) {
            oneIndex--; // Decrement oneIndex if current element is 1
        } else {
            swap(nums[zeroIndex], nums[oneIndex]); // Swap elements at zeroIndex and oneIndex
        }
    }
}

int main() {
    vector<int> nums = {1, 0, 1, 0, 1, 0, 0, 1}; // Test array
    sortBinaryArray(nums); // Sort the binary array

    // Print the sorted array
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

0 0 0 0 1 1 1 1

Explanation:

The function sortBinaryArray utilizes two pointers to segregate 0s and 1s in the array. 

The zeroIndex pointer is used to place 0s at the beginning, while the oneIndex pointer is used to place 1s at the end. When these pointers meet, it indicates that all 0s are to the left, and all 1s are to the right, achieving the sorted array. 

This method is efficient as it only requires a single traversal of the array (O(n) time complexity) and does not use extra space, fulfilling the problem's constraints.