The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

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)