Arrays & Strings

Problem 
Sort an array of 0s & 1s, i.e element at each index of the array is either 0 or 1. Implement an efficient algorithm so that the array gets sorted (all ‘0’s are placed before ‘1’s)

Solution 
First approach that we might think of is counting the no. of ‘0’s (say ‘m’) and ‘1s’ (say ‘n’) and then placing m ‘0’s and n ‘1’s. Well, this approach is efficient with complexity of O(n) but it requires traversing the array 2 times. So, as soon as you suggest this approach, interviewer would ask for a better solution.
Following implementation sorts the array in 1 pass.
Say ‘i’ points to index 0 & ‘j’ points to index n-1.
We will start traversing from end of the array.
If arr(j) is 0, then swap arr(i) & arr(j) and increment ‘i’ else decrement ‘j’.
In this way all 0s will form one portion of the array and all 1s will form other portion.

#include<iostream>
using namespace std;

// swap elements of two indexes in the array
void swap (int arr[], int pos1, int pos2) {
   int temp = arr[pos1];
   arr[pos1] = arr[pos2];
   arr[pos2] = temp;
}

// sort the array of 0 & 1 in 1 pass with no extra space
void sort01(int arr[], int size) {
   int j = size-1;
   int i = 0;
   // start traversing the array from end
   while (j >= i ) {
      if (arr[j] == 0) {
         // move the 0 to the portion of array 
         // where all 0s present and increase the 
         // '0' boundary towards right
         swap(arr,i,j);
         i++;
      }
      else {
         // don't do anything if '1' is found
         j--;
      }
   }
}

// display the array
void displayArray(int arr[],int size) {
   int i;
   for(i=0;i<size;i++)
      cout<<arr[i]<<" ";
   cout<<endl;
}

// main
int main() {
   int arr[] = {0,1,0,1,1,0,1,0,0,1,0};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"\nOriginal Array :-";
   displayArray(arr,size);
   sort01(arr,size);
   cout<<"\nSorted Array :-";
   displayArray(arr,size);
   cout<<endl;
}

Back | Next

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j – i ) s.t arr(j) > arr(i)
About    Contact    Sitemap    Terms    Privacy