703289. Segregate 0s and 1s
Segregate 0s and 1s
Summary
Given an array of integers containing only zeros and ones, segregate all occurrences of 0s and 1s. This problem requires manipulation of arrays and data structures to achieve the desired outcome.
Detailed Explanation
To solve this problem, we can use a simple algorithm that iterates through the array once. We maintain two pointers - one for 0s (or low) and one for 1s (or high). The idea is to keep track of the positions where 0s and 1s should be placed in the final array.
Here's the step-by-step breakdown:
- Initialize two pointers,
lowandhigh, both pointing to the beginning of the array. - Iterate through the array:
- If the current element is 0, move the
lowpointer one step forward and swap the element atlowwith the current element. - If the current element is 1, move the
highpointer one step backward (since we've already processed elements to its right) and swap the element athighwith the current element.
- If the current element is 0, move the
- Continue iterating until all elements have been processed.
The final array will contain all 0s followed by all 1s.
Time Complexity: O(n), where n is the length of the input array.
Space Complexity: O(1), as we only use a few extra variables to store the pointers and don't allocate any additional space proportional to the input size.
Optimized Solutions
Java
public class Segregate0sAnd1s {
public static void segregate(int[] arr) {
int low = 0, high = arr.length - 1;
while (low <= high) {
if (arr[low] == 0) low++;
else if (arr[high] == 1) high--;
else {
swap(arr, low++, high--);
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}