.png)
Sort an Array of 0s and 1s
Problem Statement
Given an array consisting only of 0s and 1s, sort the array such that:
- All 0s appear before all 1s
- The sorting should ideally be done in-place
This is a special case of array sorting and is commonly asked in coding interviews.
Example 1
Input
arr = [0, 1, 1, 0, 1, 0]
Output
[0, 0, 0, 1, 1, 1]
Example 2
Input
arr = [1, 1, 1, 0, 0]
Output
[0, 0, 1, 1, 1]
Why This Problem Is Important
This problem is used to:
- Test understanding of array traversal
- Check ability to perform in-place modifications
- Introduce the two-pointer technique
- Build logic for problems like:
- Sort 0s, 1s and 2s (Dutch National Flag)
- Segregating even and odd numbers
Approaches to Solve the Problem
- Counting Method
- Two Pointer Method (Efficient & In-Place)
Approach 1: Counting Method
Idea
- Count the number of 0s in the array
- Fill the first part of the array with 0s
- Fill the remaining part with 1s
Algorithm
- Initialize count0 = 0
- Traverse the array and count number of 0s
- Fill first count0 positions with 0
- Fill remaining positions with 1
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
C Implementation
#include<stdio.h>
int main() {
int arr[] = {0, 1, 1, 0, 1, 0};
int n = 6;
int count0 = 0;
for(int i = 0; i < n; i++) {
if(arr[i] == 0)
count0++;
}
for(int i = 0; i < count0; i++)
arr[i] = 0;
for(int i = count0; i < n; i++)
arr[i] = 1;
printf("Sorted Array: ");
for(int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Output
Sorted Array: 0 0 0 1 1 1
Approach 2: Two Pointer Method (Best Approach)
Idea
- Use two pointers:
- left starting from beginning
- right starting from end
- Move left forward when value is 0
- Move right backward when value is 1
- Swap when left points to 1 and right points to 0
Algorithm
- Initialize left = 0, right = n - 1
- While left < right:
- If arr[left] == 0, increment left
- Else if arr[right] == 1, decrement right
- Else swap arr[left] and arr[right]
- Array becomes sorted
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
C++ Implementation
#include<iostream>
using namespace std;
int main() {
int arr[] = {0, 1, 1, 0, 1, 0};
int n = 6;
int left = 0, right = n - 1;
while(left < right) {
if(arr[left] == 0)
left++;
else if(arr[right] == 1)
right--;
else
swap(arr[left], arr[right]);
}
cout << "Sorted Array: ";
for(int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Output
Sorted Array: 0 0 0 1 1 1
Java Implementation
public class SortZeroOne {
public static void main(String[] args) {
int[] arr = {0, 1, 1, 0, 1, 0};
int left = 0, right = arr.length - 1;
while (left < right) {
if (arr[left] == 0)
left++;
else if (arr[right] == 1)
right--;
else {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
System.out.print("Sorted Array: ");
for (int x : arr)
System.out.print(x + " ");
}
}
Output
Sorted Array: 0 0 0 1 1 1
Python Implementation
arr = [0, 1, 1, 0, 1, 0]
left, right = 0, len(arr) - 1
while left < right:
if arr[left] == 0:
left += 1
elif arr[right] == 1:
right -= 1
else:
arr[left], arr[right] = arr[right], arr[left]
print("Sorted Array:", arr)
Output
Sorted Array: [0, 0, 0, 1, 1, 1]
JavaScript Implementation
let arr = [0, 1, 1, 0, 1, 0];
let left = 0, right = arr.length - 1;
while (left < right) {
if (arr[left] === 0) left++;
else if (arr[right] === 1) right--;
else {
[arr[left], arr[right]] = [arr[right], arr[left]];
}
}
console.log("Sorted Array:", arr);
Output
Sorted Array: [0, 0, 0, 1, 1, 1]
Dry Run (Two Pointer Method)
| Step | Array State | Left | Right |
|---|---|---|---|
| Initial | [0,1,1,0,1,0] | 0 | 5 |
| Swap | [0,0,1,0,1,1] | 1 | 4 |
| Swap | [0,0,0,1,1,1] | 2 | 3 |
| End | Sorted | — | — |
Summary
- Problem focuses on sorting a binary array
- Two-pointer method is the most efficient
- No extra space required
- Linear time complexity
Key Takeaways
- Best Time Complexity: O(n)
- Best Space Complexity: O(1)
- Strong foundation for advanced partition problems
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
