How to segregate 0s and 1s in JavaScript

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 come to the implementation of segregating 0s and 1s in JavaScript.

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 is to 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:

Let’s proceed with the implementation process below:

Sample input

Sample output

Let's implement the code below:

Code explanation

Let’s review the code explanation below:

• Line 2–3: The code initializes two pointers, 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.

  • Line 7–8: Inside the loop, we increment the left pointer until it reaches a 1, skipping over any 0s at the beginning of the array.

  • Line 11–12: We decrement the right pointer until it reaches a 0, skipping over any 1s at the end of the array.

  • Line 15–18:  if left is less than right, we swap the values of left and right pointer. This will move all 0s to the left and all 1s to the right of the array.

• Line 23: An array arr containing 0s and 1s is initialized.

• Line 24: We call the segregateZerosAndOnes() function with the arr array to rearrange the 0s and 1s.

• Line 26: We print the rearranged array arr to the console

Time complexity

The algorithm iterates through the array once with two pointers, left and right, 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)$.