Segregate 0s and 1s

Given an array arr consisting of only 0‘s and 1‘s in random order. Modify the array in-place to segregate 0s onto the left side and 1s onto the right side of the array.

Examples :

Input: arr[] = [0, 0, 1, 1, 0]
Output: [0, 0, 0, 1, 1]
Explanation:  After segregation, all the 0's are on the left and 1's are on the right. Modified array will be [0, 0, 0, 1, 1].

Input: arr[] = [1, 1, 1, 1]
Output: [1, 1, 1, 1]
Explanation: There are no 0s in the given array, so the modified array is [1, 1, 1, 1]

Expected Time Complexity: \( O(n) \)
Expected Auxiliary Space: \( O(1) \)

Constraints:
1 ≤ arr.size() ≤ 10⁶
0 ≤ arr[i] ≤ 1

Approach 01

class Solution {
public:
    void segregate0and1(std::vector<int>& arr) {
        int count = 0;  // Initialize count of 0s in array

        // Count the number of 0s in the array
        for (int num : arr) {
            if (num == 0) {
                count += 1;
            }
        }

        // Fill the array with 0s until the count
        for (int i = 0; i < count; ++i) {
            arr[i] = 0;
        }

        // Fill the remaining array with 1s
        for (int i = count; i < arr.size(); ++i) {
            arr[i] = 1;
        }
    }
};

class Solution:
    def segregate0and1(self, arr):
        count = 0  # Initialize count of 0s in array

        # Count the number of 0s in the array
        for num in arr:
            if num == 0:
                count += 1

        # Fill the array with 0s until the count
        for i in range(count):
            arr[i] = 0

        # Fill the remaining array with 1s
        for i in range(count, len(arr)):
            arr[i] = 1

        return arr

Time Complexity

• Counting 0s:

  The first loop iterates through the entire array to count the number of 0s. This takes \( O(n) \) time, where \( n \) is the length of the array.

• Filling 0s:

  The second loop iterates from the beginning of the array up to the count of 0s. This takes \( O(count) \) time, where count is the number of 0s in the array. Since count is at most \( n \), this part also takes \( O(n) \) time.

• Filling 1s:

  The third loop iterates from the count of 0s to the end of the array, filling the remaining positions with 1s. This also takes \( O(n – count) \) time, which is at most \( O(n) \).

• Overall Time Complexity:

  Combining all parts, the overall time complexity is \( O(n) \).

Space Complexity

• Auxiliary Space:

  The algorithm uses a fixed amount of additional space for the count variable, which is \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).