Segregate 0s 1s and 2s in an Array
Segregate 0s 1s and 2s in an Array
On this page, we will explore how to segregate 0s, 1s, and 2s in an array using Java. The given problem involves an array consisting only of the elements 0, 1, and 2.
Objective is to sort the array such that all 0s come first, followed by all 1s, and then all 2s, without using any inbuilt sorting method.
We will walk through the problem in detail and implement solutions using multiple approaches, including brute force and optimized methods. Each solution will be explained with the corresponding algorithm, code implementation in Java, and an analysis of time and space complexity to ensure a thorough understanding.
Segregate 0s 1s and 2s in an Array in Java
Task at hand is to sort an array of integers that exclusively consists of 0’s, 1’s, and 2’s, with the goal of segregating them in a specific order.
Desired arrangement entails placing all the 0s before the 1s, and all the 1s before the 2s.
This particular challenge is commonly known as the Dutch National Flag problem, drawing inspiration from the three bands of color in the Dutch flag. In this discourse, we will look into two different approaches to tackle this problem.
- Brute Force Method
- Dutch National Flag Method
1. Brute Force Approach
Brute force approach to segregate 0’s, 1’s, and 2’s in an array is to count the number of 0’s, 1’s, and 2’s in the array, and then overwrite the array with the correct number of each value
Algorithm for Brute Force:
Here’s how the algorithm works:
- Initialize counters for 0’s, 1’s, and 2’s to 0.
- Loop through the array and count the occurrences of 0’s, 1’s, and 2’s.
- Store the counts in separate variables.
- Overwrite the array with the correct number of each value, starting with 0’s, then 1’s, then 2’s, using the stored counts.
Space Complexity: O(1) or O(n)
Code for Brute Force method in Java
public class Main {
public static void segregate(int arr[], int n) {
int count_0 = 0, count_1 = 0, count_2 = 0;
// Step 1: Count the number of 0's, 1's, and 2's
for (int i = 0; i < n; i++) { if (arr[i] == 0) { count_0++; } else if (arr[i] == 1) { count_1++; } else if (arr[i] == 2) { count_2++; } } // Step 2: Overwrite the array with the counted values int i = 0; while (count_0-- > 0) arr[i++] = 0;
while (count_1-- > 0) arr[i++] = 1;
while (count_2-- > 0) arr[i++] = 2;
}
public static void main(String[] args) {
int arr[] = {2, 0, 1, 2, 0, 1, 0, 2, 1};
int n = arr.length;
System.out.print("Original Array: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
segregate(arr, n);
System.out.print("Segregated Array: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
Sample Input:
int arr[] = {2, 0, 1, 2, 0, 1, 0, 2, 1};
Output:
Original Array: 2 0 1 2 0 1 0 2 1 Segregated Array: 0 0 0 1 1 1 2 2 2
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
2. Dutch National Flag Approach
One approach to segregate 0’s, 1’s, and 2’s in an array is to use the Dutch National Flag algorithm. The basic idea of this algorithm is to maintain three pointers to partition the array into three parts: the 0’s, the 1’s, and the 2’s.
Algorithm for Dutch National Flag Algorithm
Here’s how the algorithm works:
- Initialize three pointers –
lowpointing to the beginning of the array,midpointing to the current element being processed, andhighpointing to the end of the array. - While
midis less than or equal tohigh, repeat steps 3-7. - Check if the value at
arr[mid]is 0. - If yes, swap the values at
arr[mid]andarr[low], and increment bothmidandlow. - If the value at
arr[mid]is 1, movemidpointer to the next element. - If the value at
arr[mid]is 2, swap the values atarr[mid]andarr[high], and decrementhigh. - Repeat steps 3-6 until
midbecomes greater thanhigh. - The array is now segregated with 0’s on the left, 1’s in the middle, and 2’s on the right.
Space Complexity: O(1)
Code for Dutch National Flag Method in Java
public class Main {
public static void dutchNationalFlag(int[] arr, int n) {
int low = 0;
int mid = 0;
int high = n - 1;
while (mid <= high) {
if (arr[mid] == 0) {
// Swap arr[low] and arr[mid]
int temp = arr[mid];
arr[mid] = arr[low];
arr[low] = temp;
low++;
mid++;
} else if (arr[mid] == 1) {
mid++;
} else {
// Swap arr[mid] and arr[high]
int temp = arr[mid];
arr[mid] = arr[high];
arr[high] = temp;
high--;
}
}
}
public static void main(String[] args) {
int[] arr = {2, 0, 1, 2, 0, 1, 0, 2, 1};
int n = arr.length;
System.out.print("Original Array: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
dutchNationalFlag(arr, n);
System.out.print("Segregated Array: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
Sample Input:
int[] arr = {2, 0, 1, 2, 0, 1, 0, 2, 1};
Output:
Original Array: 2 0 1 2 0 1 0 2 1 Segregated Array: 0 0 0 1 1 1 2 2 2
Conclusion
In this problem, we learned how to segregate 0s, 1s, and 2s in an array using two approaches.
- Brute Force method is easy to understand. It works by counting each number and then rewriting the array. But it takes two passes through the array.
- Dutch National Flag algorithm is more efficient. It solves the problem in just one pass using only constant space and works in-place, making it better for larger arrays.
So, if you’re looking for a quick and optimized solution, the Dutch National Flag method is the best choice.
FAQ's related to Segregate 0s 1s and 2s in an Array
Answer:
- It means arranging all the 0’s first, followed by all the 1’s, and then all the 2’s in the array.
- Order within each group doesn’t matter — only the group sequence (0s → 1s → 2s) is important.
Answer:
Dutch National Flag Algorithm is an efficient sorting technique invented by Edsger Dijkstra. It is specifically designed to sort an array of 0s, 1s, and 2s in a single traversal and in-place, without using any extra space.
The algorithm uses three pointers:
- low – for the next position of 0
- mid – to process the current element
- high – for the next position of 2
Answer:
Yes, you can use methods like Arrays.sort(), but it’s not optimal. Since the array only contains 0, 1, and 2, it’s better to use custom sorting techniques like the brute force method or Dutch National Flag algorithm, which are more efficient for this use case.
Answer:
Most efficient and recommended approach is the Dutch National Flag algorithm.
It works in O(n) time and O(1) space, making it ideal for in place array sorting in Java when dealing with arrays containing only 0s, 1s, and 2s.
Answer:
- Problem is popular in Java programming interviews because it tests skills in array manipulation, pointer handling, in place algorithms, and time space optimization.
- It’s also a good way to evaluate how candidates approach real world array problems under constraints.
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
Can’t we use Arrays.sort(arr)
where arr is input arr given by user