# Sort an array of 0s and 1s

Problem Statement: Given an array of length N consisting of only 0s and 1s in random order. Modify the array to segregate 0s on the left and 1s on the right side of the array.

Note: (instead of 0s and 1s we can  also be given with an array of any 2 random integers)

Examples:

```Example 1:
Input: N = 5, arr[ ] = {1,0,1,1,0}
Output: {0,0,1,1,1}

Example 2:
Input: N  = 5 , arr[ ] = {1,0,0,0,1}
Output: {0,0,0,1,1}
```

### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

### Solution 1:

Approach:

• We will traverse the entire array and count the number of 0s ,
• Once we get the number of zeroes , we can easily the count of 1s as arr.size(_) – count_of_0s
• Now we will simply fill the array , first we will fill it with 0s till the count_of_0s , then we will fill the 1s

Code:

## C++ Code

``````#include <bits/stdc++.h>

using namespace std;
class Solution {
public:

void segregate0and1(int arr[], int n) {
int count = 0;

for (int i = 0; i < n; i++) {
if (arr[i] == 0)
count++;
}

for (int i = 0; i < count; i++)
arr[i] = 0;

for (int i = count; i < n; i++)
arr[i] = 1;
}
};

int main() {
int n = 5;
int arr[]={1,0,1,0,1};
Solution ob;
cout << "Before Sorting: ";
for (int a: arr)
cout << a << " ";
cout << endl;
ob.segregate0and1(arr, n);
cout << "After Sorting: ";
for (int a: arr)
cout << a << " ";
}``````

Output:

Before Sorting: 1 0 1 0 1
After Sorting: 0 0 1 1 1

Time Complexity: O(n)

Space Complexity: O(1)

## Java Code

``````import java.util.*;

class Solution {

static void segregate0and1(int arr[], int n) {
int count = 0;

for (int i = 0; i < n; i++) {
if (arr[i] == 0)
count++;
}

for (int i = 0; i < count; i++)
arr[i] = 0;

for (int i = count; i < n; i++)
arr[i] = 1;
}

public static void main(String args[]) {
int n = 5;
int arr[]={1,0,1,0,1};
System.out.print("Before Sorting: ");
for (int a: arr)
System.out.print(a + " ");
System.out.println();
segregate0and1(arr, n);
System.out.print("After Sorting: ");
for (int a: arr)
System.out.print(a + " ");
}
}``````

Output:

Before Sorting: 1 0 1 0 1
After Sorting: 0 0 1 1 1

Time Complexity: O(n)

Space Complexity: O(1)

### Solution 2:

Approach: Two pointer approach

• Take 2 pointers say s  and e ,one at the beginning and the other at the end of the array
• Let s point at the beginning of the array and e at the end .
• Now we want to put all the 1s in the right side of the array , once we do this all 0s will automatically be on the left side of the array
• So we compare the elements at s , arr[s] =1 then this should be at the right side of the array , so we swap this with element present at e
• After swapping , now we know that element at index e will surely be 1 , so now we can decrement e .
• Else if theres a 0 then we will increment i

Code:

## C++ Code

``````#include <bits/stdc++.h>

using namespace std;
class Solution {
public:

void segregate0and1(int arr[], int n) {
int type0 = 0;
int type1 = n - 1;

while (type0 < type1) {
if (arr[type0] == 1) {
swap(arr[type0], arr[type1]);
type1--;
} else {
type0++;
}
}
}
};

int main() {
int n = 5;
int arr[]={1,0,1,0,1};
Solution ob;
cout << "Before Sorting: ";
for (int a: arr)
cout << a << " ";
cout << endl;
ob.segregate0and1(arr, n);
cout << "After Sorting: ";
for (int a: arr)
cout << a << " ";
}``````

Output:

Before Sorting: 1 0 1 0 1
After Sorting: 0 0 1 1 1

Time Complexity: O(n)

Space Complexity: O(1)

## Java Code

``````import java.util.*;

class Solution {

static void segregate0and1(int arr[], int n) {
int type0 = 0;
int type1 = n - 1;
int temp;
while (type0 < type1) {
if (arr[type0] == 1) {
temp = arr[type0];
arr[type0] = arr[type1];
arr[type1] = temp;
type1--;
} else {
type0++;
}
}
}

public static void main(String args[]) {
int n=5;
int arr[]={1,0,1,0,1};
System.out.print("Before Sorting: ");
for (int a: arr)
System.out.print(a+" ");
System.out.println();
segregate0and1(arr, n);
System.out.print("After Sorting: ");
for (int a: arr)
System.out.print(a+" ");
}
}``````

Output:

Before Sorting: 1 0 1 0 1
After Sorting: 0 0 1 1 1

Time Complexity: O(n)

Space Complexity: O(1)