Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

Segregate 0’s and 1’s and 2’s in array.

Given an array with 0’s, 1’s and 2’s, we are segregating the 0’s, 1’s and 2’s.

INPUT

0 1 2 0 1 1 1 1 1 0 1 2 1 0 2 2 2 0 1 2 0 1

OUTPUT

0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2

 

Method 1:-

TIME COMPLEXITY – O(N)
SPACE COMPLEXITY – O(1)

1. Simply create an count_array of size 3 and initialize all the element of the array to be zero.
2. The array element of count_array depicts the number of occurences of index i.
3. Traverse the given array and if we get 0 increment the 0th index of count_array and similarly do for 1 and 2 by incrementing the value count_array of 1st and 2nd index.
4. Finally print the number of 0’s , 1’s and 2’s as many times as the value of element of count_array.

code:-

[code language=” cpp”]

#include <bits/stdc++.h>

using namespace std;

int main()

{

int arr[] = {1,0,2,1,0,1,2,0,1,2,0,1,1,1,0,2,0,2,2,0,1,2};//array

int N = sizeof(arr)/sizeof(arr[0]);//size of array

int count[3]={0};

for(int i=0;i<N;i++)

count[arr[i]]++;//increase the count of that index

for(int i=0;i<3;i++)

for(int j=0;j<count[i];j++)//print that index as many times its value is
cout<<i<<" ";
return 0;
}

[/code]

 

Method 2:-

The approach we need to follow for segregating 0’s 1’s and 2’s is that we maintain 3 pointers.

code:-

[code language=”cpp”]

#include <iostream>
using namespace std;

void swap(int *a, int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
int main() {
// your code goes here
int i;
int arr[] = {1,0,2,1,0,1,2,0,1,2,0,1,1,1,0,2,0,2,2,0,1,2};

int N=sizeof(arr)/sizeof(arr[0]);
int lo=0;
int mid=0;
int high=N-1;
while(mid<=high)
{
if(arr[mid]==0)
swap(arr[lo++],arr[mid]);
else if(arr[mid]==1)
mid++;
else
swap(arr[mid],arr[high–]);

}

for(i=0;i<N;i++)
cout<<arr[i]<<" ";
cout<<endl;

return 0;
}

[/code]

One comment on “Segregate 0’s and 1’s and 2’s in array.”


  • Abhishek

    #include
    using namespace std;
    int segregate(int a[],int n)
    {
    int count1=0;
    int count2=0;
    for(int i=0;i<n;i++)
    {
    if(a[i]==0)
    {
    count1++;
    }
    if(a[i]==1)
    {
    count2++;
    }
    }
    for(int i=0;i<count1;i++)
    {
    a[i]=0;
    }
    for(int i=count1;i<(count1+count2);i++)
    {
    a[i]=1;
    }
    for(int i=(count1+count2);i<n;i++)
    {
    a[i]=2;
    }
    }
    int main()
    {
    int a[12]={0,1,2,0,1,2,0,1,2,0,1,2};
    int n=sizeof(a)/sizeof(a[0]);
    segregate(a,n);
    for(int i=0;i<n;i++)
    {
    cout<<a[i];
    }
    }
    check it out!!