How to segregate 0s and 1s in an array in Java

Suppose we’re working on a project that deals with binary data where 0 represents one state and 1 represents another. 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 segregation of 0s and 1s in Java.

Implementation of segregation of 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, we can 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 toward 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:

public class main {
    public static void segregateZerosAndOnes(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            // Increment left pointer while there are 0s at the beginning
            while (arr[left] == 0 && left < right) {
                left++;
            }
            // Decrement right pointer while there are 1s at the end
            while (arr[right] == 1 && left < right) {
                right--;
            }
            // Swap 0 at the left pointer with 1 at the right pointer
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {0, 1, 0, 1, 1, 0, 0, 1};
        segregateZerosAndOnes(arr);
        System.out.print("Segregated Array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Code explanation

Lines 3–4: Set left to the start of the array and right to the end of the array.
Line 6: The while loop will continue until the left is less than the right.
Lines 8–10: Move the left pointer to the right until it points to a 1 (skipping 0s).
Lines 13–15: Move the right pointer to the left until it points to a 0 (skipping 1s).
Lines 18–24: 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 29: The arr is initialized with 0s and 1s.
Line 30: This line includes calling the function segregateZerosAndOnes() and passing the array arr to rearrange 0s and 1s.
Lines 31–34: These lines include printing the array arr element on the 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)$ .

Conclusion

Using the two-pointer technique, the array of binary numbers is efficiently segregated so that all 0s come before all 1s. This approach optimizes space usage and has a linear time complexity, making it suitable for various applications involving binary data processing.

Free Resources