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.

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

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.

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:

[0, 1, 0, 1, 1, 0, 0, 1]

[0, 0, 0, 0, 1, 1, 1, 1]

Let's implement the code below:

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

**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.

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

The algorithm uses only a constant amount of extra space for both pointers, leading to a space complexity of

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS