Segregate 0’s and 1’s in array

Segregate 0s and 1s in Array in Java

In this article, we will learn about how to segregate 0s and 1s in array in Java with detailed procedure and code. In the given array, we will try to separate 0’s and 1’s from each other using two different methods.

Go through this page to get complete to know about complete process to Segregate 0s and 1s in array in java with both approaches, i.e: Counting Zeroes and Two Pointer Technique.

Segregate 0s and 1s in an array in Java

Segregate 0s and 1s in an array in Java

Example:

Segregating 0’s and 1’s in an array involves rearranging the elements so that all the 0’s come before all the 1’s.

For instance, given an array [1, 0, 0, 1, 1, 0], segregating 0’s and 1’s would yield [0, 0, 0, 1, 1, 1].

This type of segregation is commonly applied in computer science and programming for handling binary data or flags, and it can also be used as a preprocessing step in machine learning algorithms for binary classification problems.

Segregate 0’s and 1’s in an array in Java

Example Problem Statement:

Given: An array of only 0’s and 1’s.

Goal: Rearrange the array so that all 0’s appear on the left side and all 1’s on the right side.

Example:

Input:

int[] arr = {0, 1, 1, 0, 1, 0, 0, 1};

Output:

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

Approach 1: Count and Overwrite Method

Idea:

Count the number of 0’s and then overwrite the original array:

  • First fill the array with that many 0’s
  • Then fill the rest with 1’s

Algorithm:

  1. Initialize a counter count = 0.

  2. Traverse the array.

  3. For every element equal to 0, increment count.

  4. Loop from i = 0 to count - 1, set arr[i] = 0.

  5. Loop from i = count to arr.length - 1, set arr[i] = 1.

Segregate 0s and 1s in an array in Java Programming

Code Implementation:

Run
import java.util.Arrays;

public class SegregateZeroOne {
    public static void segregateCountMethod(int[] arr) {
        int count = 0;

        // Step 1: Count 0’s
        for (int num : arr) {
            if (num == 0) {
                count++;
            }
        }

        // Step 2: Fill 0’s
        for (int i = 0; i < count; i++) {
            arr[i] = 0;
        }

        // Step 3: Fill 1’s
        for (int i = count; i < arr.length; i++) {
            arr[i] = 1;
        }
    }

    public static void main(String[] args) {
        int[] arr = {0, 1, 1, 0, 1, 0, 0, 1};
        segregateCountMethod(arr);
        System.out.println("Output using Count Method: " + Arrays.toString(arr));
    }
}

Output:

Output using Count Method: [0, 0, 0, 0, 1, 1, 1, 1]

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Approach 2: Two Pointer (In Place Swap)

Idea:

Use two pointers:

  • Start one from the beginning (left)
  • One from the end (right)
  • Swap if arr[left] == 1 and arr[right] == 0.

Algorithm:

  1. Initialize left = 0 and right = arr.length - 1

  2. While left < right:

    • If arr[left] == 0, increment left

    • If arr[right] == 1, decrement right

    • If arr[left] == 1 and arr[right] == 0, swap them and move both pointers

Segregate 0s and 1s in an array in Java Programming

Code Implementation:

Run
import java.util.Arrays;

public class SegregateZeroOneTwoPointer {
    public static void segregateInPlace(int[] arr) {
        int left = 0, right = arr.length - 1;

        while (left < right) {
            // Move left if current is 0
            while (arr[left] == 0 && left < right) {
                left++;
            }

            // Move right if current is 1
            while (arr[right] == 1 && left < right) {
                right--;
            }

            // Swap when left is 1 and right is 0
            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, 1, 0, 1, 0, 0, 1};
        segregateInPlace(arr);
        System.out.println("Output using Two-Pointer Method: " + Arrays.toString(arr));
    }
}

Output:

Output using Two-Pointer Method: [0, 0, 0, 0, 1, 1, 1, 1]

Summary

  • Segregating 0’s and 1’s is a foundational array manipulation problem.
  • It’s commonly used in sorting binary arrays or preprocessing data.

Two main approaches:

  • Count and overwrite
  • In place swap using two pointers

Learn DSA

FAQ's related to Segregate 0s and 1s in an array

Answer:

  • Reordering an array using indexes means rearranging its elements based on a separate index array.
  • Each value in the index array tells where the corresponding element from the original array should go.

Answer:

You can create a temporary array and place each element from the original array into the position specified by the index array. Then copy the result back to the original array if needed.

Answer:

Yes, it is possible using in place cyclic swaps. However, this method is more complex and can be harder to implement correctly.

It modifies both the array and the index array during execution.

 

Answer:

Using an extra array, the time complexity is O(n) and space complexity is O(n). The in-place version has O(1) space complexity but may have higher time complexity if not optimized.

Answer:

Yes, the index array should contain unique integers from 0 to n-1. Duplicate or out of-bound values can lead to incorrect or undefined behavior.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription