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.
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:
Initialize a counter
count = 0.Traverse the array.
For every element equal to 0, increment
count.Loop from
i = 0 to count - 1, setarr[i] = 0.Loop from
i = count to arr.length - 1, setarr[i] = 1.
Space Complexity: O(1)
Segregate 0s and 1s in an array in Java Programming
Code Implementation:
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:
Initialize
left = 0andright = arr.length - 1While
left < right:If
arr[left] == 0, incrementleftIf
arr[right] == 1, decrementrightIf
arr[left] == 1andarr[right] == 0, swap them and move both pointers
Space Complexity: O(1)
Segregate 0s and 1s in an array in Java Programming
Code Implementation:
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
Login/Signup to comment