.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)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
