How to segregate 0s and 1s in Python

Suppose we’re working on a project that deals with binary data. where 0 represents one state and 1 represents the other. 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 now come to the implementation of segregating 0s and 1s in Python.

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, 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 towards 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:

def segregate_zeros_and_ones(array):
    left = 0
    right = len(array) - 1
    while left < right:
        # Move left pointer to the right until it points to a 1
        while array[left] == 0 and left < right:
            left += 1
        # Move right pointer to the left until it points to a 0
        while array[right] == 1 and left < right:
            right -= 1
        # Swap 0 at left pointer with 1 at right pointer
        if left < right:
            array[left], array[right] = array[right], array[left]
            left += 1
            right -= 1
# Example usage
array = [0, 1, 0, 1, 1, 0, 0, 1]
segregate_zeros_and_ones(array)
print(array)

Code explanation

Lines 2–3: Set left to the start of the array and right to the end of the array.

Line 5: The while loop will continue until the left is less than the right.

Lines 7– 8: Move the left pointer to the right until it points to a 1 (skipping 0s).

Lines 11–12: Move the right pointer to the left until it points to a 0 (skipping 1s)

Lines 15–18: If left is still less than right, swap the values at the left and right pointers. This puts a 0 on the left side and a 1 on the right side.

Line 21: array is initialized with 0s and 1s.

Line 22: Calling the function segregate_zeros_and_ones() and passing the array to rearrange 0s and 1s.

Line 23: Printing the array element on 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)$ .

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments