Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Brute Force approach - (Count 0s or 1s) 
3.1.
Steps of Algorithm
3.2.
Implementation
3.3.
C++
3.4.
Java
3.5.
Python
3.6.
Javascript
3.7.
C#
3.8.
Complexity Analysis
4.
Optimized Approach - (Use two indexes to traverse)
4.1.
Steps of Algorithm
4.2.
Implementation
4.3.
C++
4.4.
Java
4.5.
Python
4.6.
Javascript
4.7.
C#
4.8.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
How to segregate 0 and 1 in an array in Java?
5.2.
How to separate 0 and 1 in an array in Python?
5.3.
How do you segregate an array?
5.4.
What is the sequence of 0s and 1s?
6.
Conclusion
Last Updated: May 9, 2024

Segregate 0s and 1s in an Array

Introduction

This article will look at the problem of segregating 0s and 1s in an array. Array-based questions are the most popular and vital in coding interviews and programming competitions. Let's understand the problem statement.

Segregate 0s and 1s in an Array

Must Read, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

We have given an array containing only 0s and 1s in random order, and we have to segregate 0s on the left side and 1s on the right side of the array.

Sample Examples

Input 1: 

a[] = {0, 1, 0, 1, 0, 1, 0, 1}

 

Output 1:

{ 0, 0, 0, 0, 1, 1, 1, 1}

 

Explanation: Since basically we have to sort the array. So after sorting the 0s are moved to the left and all the 1s are transferred to the right.


Input 2: 

a[] = {1,1,1,1}

 

Output 2:

{1,1,1,1}

Explanation: Here we only have 1s so the array remains intact as after moving all 1s to right it still resembles the original array.

Also read, Array in Java

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Brute Force approach - (Count 0s or 1s) 

In this method we will first count the number of 0s and 1s and fill the array accordingly.

Steps of Algorithm

  1. Suppose the array is {0,1,0,1, 0}. The size of the array is 4. We will first count the number of 0s which in this case is 2. Now we can get the number of 1s by subtracting the number of 0s from the size. (5-3=2)
  2. Once we have counted the 0s and 1s, we can fill the array. First we will fill the zeros and then ones (we can get number of ones by using the above formula). 

Implementation

  • C++
  • Java
  • Python
  • Javascript
  • C#

C++

#include <bits/stdc++.h>
using namespace std;
void segregating0sand1s(int arr[], int n)
{
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 0) // to counts the no of zeros in arr
count++;
}

for (int i = 0; i < count; i++)
arr[i] = 0; // loop to fill the arr with 0 until count
for (int i = count; i < n; i++)
arr[i] = 1; // loop to fill remaining arr space with 1
}

void print(int arr[], int n)
{
cout << "Array after segregating 0s and 1s is ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}

// Driver function
int main()
{
int arr[] = { 1, 1, 0, 1, 0, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
segregating0sand1s(arr, n);
print(arr, n);
return 0;
}

Java

public class SegregateZerosOnes {
static void segregating0sand1s(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;
}

static void print(int[] arr, int n) {
System.out.print("Array after segregating 0s and 1s is ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}

public static void main(String[] args) {
int[] arr = {1, 1, 0, 1, 0, 1};
int n = arr.length;
segregating0sand1s(arr, n);
print(arr, n);
}
}

Python

def segregating0sand1s(arr):
count = arr.count(0)
arr[:count] = [0] * count
arr[count:] = [1] * (len(arr) - count)

def print_array(arr):
print("Array after segregating 0s and 1s is", end=" ")
for num in arr:
print(num, end=" ")

arr = [1, 1, 0, 1, 0, 1]
segregating0sand1s(arr)
print_array(arr)

Javascript

function segregating0sand1s(arr) {
const count = arr.filter(num => num === 0).length;
arr.fill(0, 0, count);
arr.fill(1, count);
}

function printArray(arr) {
process.stdout.write("Array after segregating 0s and 1s is ");
for (let i = 0; i < arr.length; i++) {
process.stdout.write(arr[i] + " ");
}
}

const arr = [1, 1, 0, 1, 0, 1];
segregating0sand1s(arr);
printArray(arr);

C#

using System;

class SegregateZerosOnes {
static void Segregating0sand1s(int[] arr) {
int count = 0;
foreach (int num in arr) {
if (num == 0)
count++;
}
for (int i = 0; i < count; i++)
arr[i] = 0;
for (int i = count; i < arr.Length; i++)
arr[i] = 1;
}

static void Print(int[] arr) {
Console.Write("Array after segregating 0s and 1s is ");
foreach (int num in arr) {
Console.Write(num + " ");
}
}

static void Main(string[] args) {
int[] arr = {1, 1, 0, 1, 0, 1};
Segregating0sand1s(arr);
Print(arr);
}
}

Output:

Array after segregating 0s and 1s is 0 0 1 1 1 1.

 

Complexity Analysis

The time complexity is O(n).

The space complexity is O(1).

The above approach traverses the array two times. Below we will talk of a more optimized solution which traverses array single time.

Optimized Approach - (Use two indexes to traverse)

This approach traverses the array only once. Here we maintain two indexes where the left index is initialized as 0 and the right index as n-1. We then check the conditions and move the pointers accordingly.

Steps of Algorithm

while (left < right)

  1. Keep incrementing index left if it is equal to 0s 
  2. Keep decrementing index right if it is equal to 1s
  3. If left < right then we will exchange arr[left] and arr[right]

Implementation

  • C++
  • Java
  • Python
  • Javascript
  • C#

C++

#include <bits/stdc++.h>
using namespace std;

void segregating0sand1s(int arr[], int size)
{
int left = 0, right = size-1;

while (left < right)
{
while (arr[left] == 0 && left < right)
left++;

while (arr[right] == 1 && left < right)
right--;

if (left < right)
{
arr[left] = 0;
arr[right] = 1;
left++;
right--;
}
}
}

/* Driver code */
int main()
{
int arr[] = {1, 1, 0, 1, 1, 0};
int i, arr_size = sizeof(arr)/sizeof(arr[0]);
segregating0sand1s(arr, arr_size);
cout << "Array after segregating 0s and 1s is ";
for (i = 0; i < 6; i++)
cout << arr[i] << " ";
return 0;
}

Java

public class SegregateZerosOnes {
static void segregating0sand1s(int[] arr) {
int left = 0, right = arr.length - 1;

while (left < right) {
while (arr[left] == 0 && left < right)
left++;

while (arr[right] == 1 && left < right)
right--;

if (left < right) {
arr[left] = 0;
arr[right] = 1;
left++;
right--;
}
}
}

public static void main(String[] args) {
int[] arr = {1, 1, 0, 1, 1, 0};
segregating0sand1s(arr);
System.out.print("Array after segregating 0s and 1s is ");
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
}

Python

def segregating0sand1s(arr):
left, right = 0, len(arr) - 1
while left < right:
while arr[left] == 0 and left < right:
left += 1
while arr[right] == 1 and left < right:
right -= 1
if left < right:
arr[left] = 0
arr[right] = 1
left += 1
right -= 1

arr = [1, 1, 0, 1, 1, 0]
segregating0sand1s(arr)
print("Array after segregating 0s and 1s is", end=" ")
print(*arr)

Javascript

function segregating0sand1s(arr) {
let left = 0, right = arr.length - 1;

while (left < right) {
while (arr[left] === 0 && left < right)
left++;

while (arr[right] === 1 && left < right)
right--;

if (left < right) {
arr[left] = 0;
arr[right] = 1;
left++;
right--;
}
}
}

const arr = [1, 1, 0, 1, 1, 0];
segregating0sand1s(arr);
process.stdout.write("Array after segregating 0s and 1s is ");
console.log(arr.join(" "));

C#

using System;

class SegregateZerosOnes {
static void Segregating0sand1s(int[] arr) {
int left = 0, right = arr.Length - 1;

while (left < right) {
while (arr[left] == 0 && left < right)
left++;

while (arr[right] == 1 && left < right)
right--;

if (left < right) {
arr[left] = 0;
arr[right] = 1;
left++;
right--;
}
}
}

static void Main(string[] args) {
int[] arr = {1, 1, 0, 1, 1, 0};
Segregating0sand1s(arr);
Console.Write("Array after segregating 0s and 1s is ");
foreach (int num in arr) {
Console.Write(num + " ");
}
}
}

Output:

Array after segregating 0s and 1s is 0 0 1 1 1 1.

 

Complexity Analysis

The time complexity is O(n).

The space complexity is O(1).

Frequently Asked Questions

How to segregate 0 and 1 in an array in Java?

To segregate 0s and 1s in Java, iterate through the array, moving 0s to the beginning and 1s to the end.

How to separate 0 and 1 in an array in Python?

To separate 0s and 1s in Python, use two pointers, one from the start and one from the end, swapping 0s and 1s until pointers meet.

How do you segregate an array?

To segregate an array, iterate through it, moving specific elements based on a condition, such as separating 0s and 1s.

What is the sequence of 0s and 1s?

The sequence of 0s and 1s in an array depends on the segregation process applied, where either 0s precede 1s or vice versa.

Conclusion

This article discussed the solution for segregating 0s and 1s in an array along with its different approaches, pseudocode, implementation, and code in both JAVA and C++.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Recommended Problems - 

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Given a Sorted and Rotated Array, Find if There is a Pair with a Given Sum
Next article
Rearrange positive and negative using the inbuilt sort function
Live masterclass