Segregate 0s and 1s Problem in Java

It is a problem frequently asked in interviews of top IT companies like Google, Amazon, TCS, Accenture, Flipkart etc. By solving the problem, one wants to check the logical ability, critical thinking, and problem-solving skill of the interviewee. So, in this section, we are going to find the Separate 0s and 1s problem with different approaches and logic. Also, we will create Java programs for the same.

The Separate 0s and 1s problem simply rearranges the array of 0s and 1s so that all 0s appear on one side. (usually on the left) and both 1 will appear on the other side. This problem is often considered a form of the two-pecker technique and is a fundamental question of array manipulation.

This problem is essential for understanding basic sorting techniques, working with limited values in arrays, and implementing in-place algorithms with minimal time complexity.

Example

Input Array: {0, 1, 1, 0, 1, 0, 0, 1, 1, 0}

Initial State:

• left = 0, right = 9 (Start and end indices)
• Array: {0, 1, 1, 0, 1, 0, 0, 1, 1, 0}

Iteration 1:

• arr[left] = 0 (Already correct, increment left to 1).
• arr[right] = 0 (Swap with arr[left]).
• Array after swap: {0, 0, 1, 0, 1, 0, 0, 1, 1, 1}

Iteration 2:

• left = 2, right = 8.
• arr[left] = 1, arr[right] = 1 (Decrement right to 7).

Iteration 3:

• left = 2, right = 7.
• arr[left] = 1, arr[right] = 0 (Swap).
• Array after swap: {0, 0, 0, 0, 1, 1, 1, 1, 1, 1}

End:

• Pointers meet at index 5; loop ends.
• Final Array: {0, 0, 0, 0, 1, 1, 1, 1, 1, 1}

Approaches to Solve the Problem

1. Naive Approach (Counting)
   
   • Count the number of 0s and 1s inside the array.
   • Overwrite the array by first placing all 0s accompanied via all 1s.
   • Time Complexity: (O(n))
   • Space Complexity: (O(1))
2. Efficient Approach (Two Pointer Technique)
   
   • Use two pointers. One starts from the left side and the other from the right side.
   • Move the left pointer until you find a 1.
   • Move the right pointer until you find a 0.
   • Swap the elements at these pointers and continue until the pointers meet.
   • Time Complexity: (O(n))
   • Space Complexity: (O(1))

File Name: SegregateZerosAndOnes.java

Output:

 
Original Array:
0 1 1 0 1 0 0 1 1 0 
Array after segregation:
0 0 0 0 0 1 1 1 1 1    

Explanation

The given Java program segregates 0s and 1s in an array using the two-pointer technique, ensuring an efficient and in place solution. It initializes two pointers, left at the start and right at the end of the array.

The left pointer moves forward facing 0 seconds because it is in the correct position. and the right pointer moves backward facing for 1 second. When arr[left] is 1 and arr[right] is 0, both values are switched to their correct positions. and both pointers will move inward.

This process continues until the pointers meet, resulting in all 0s on the left and all 1s on the right. This approach guarantees a time complexity (O(1)) with space (O(1)), making it highly efficient and suitable for binary arrays.

Advantages of the TwoPointer Technique

1. Time Efficient:
   The array is traversed only once, making the algorithm (O(n)).
2. Space Efficient:
   The technique uses constant extra space ((O(1))) since all operations are done inplace.
3. Simplicity:
   The logic is straightforward and avoids the overhead of additional data structures.

Use Cases

1. Binary Sorting: Rearranging binary arrays in networking and hardware applications.
2. Preprocessing: Before applying advanced algorithms like searching or indexing, segregating data can simplify logic.
3. Other Segregation Problems: It can be adapted for partitioning arrays based on other criteria (e.g., negative and positive numbers).

Complexity Analysis

1. Time Complexity

The algorithm traverses the array once, making comparisons and swaps in constant time for each element.

• Best Case: (O(n)) (Already sorted, with no swaps required).
• Worst Case: (O(n)) (Maximum swaps needed, but still linear traversal).
• Average Case: (O(n)) (Linear traversal regardless of input order).

2. Space Complexity

The algorithm operates entirely inplace, requiring no additional memory.

• Auxiliary Space: (O(1)), as it uses only two pointers and a temporary variable for swapping.

3. Optimized Efficiency

The constant space and linear time complexity make the algorithm highly efficient, especially when working with large arrays. It avoids the overhead of using extra data structures, offering a performance advantage in memoryconstrained systems.

Conclusion

The "Segregate 0s and 1s" problem demonstrates the power of inplace sorting using the twopointer technique. It efficiently rearranges a binary array without requiring additional space, ensuring all 0s are positioned to the left and all 1s to the right.

The approach is simple yet optimal, making it suitable for both beginner and advanced programmers. By minimizing traversals and swaps, it highlights the importance of optimizing algorithms for time and space complexity, especially for large datasets.

This solution is robust and can serve as the foundation for solving more complex segregation problems.