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 & 2s, i.e element at each index of the array is either 0, 1 or 2 and we need to place all 0s first, then 1s and finally all 2s.

Solution :-
After implementing an efficient algorithm to sort an array of 0s & 1s, a very common follow up question is to sort the array of 0s, 1s & 2s.
Again, we won't consider the counting approach rather would go for a 1 pass approach in which the sorting would be done by traversing the array only once.
We need to divide the array into 3 parts.
Say 'i' points to index 0 & 'j' points to index n-1.
We will start traversing from the end of array & 'k' is the iterator starting at index n-1.
If arr(k) is 0, then swap arr(i) & arr(k) and increment 'i'.
If arr(k) is 2, then swap arr(j) & arr(k) and decrement 'j'.
If arr(k) is 1, then don't do anything, simple decrement the iterator 'k'.
In this way, the array will be divided into 3 portions.

#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,2 in 1 pass with no extra space
void sort012(int arr[], int size) {
   int start = 0;
   int end = size-1;
   int j = end;
   // start traversing from end
   // maintain two pointers
   // start -> '0' boundary from left
   // end -> '2' boundary from right
   // j -> iterator
   while (j >= start) {
      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,start,j);
         start++;
      }
      else if (arr[j] == 2) {
         // move the 2 to the portion of array 
         // where all 2s present and increase the 
         // '2' boundary towards left
         swap(arr,j,end);
         end--;
      }
      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[] = {1,2,0,1,0,1,2,0,2,0,0,2,1,0,1,0};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"\nOriginal Array :-";
   displayArray(arr,size);
   sort012(arr,size);
   cout<<"\nSorted Array :-";
   displayArray(arr,size);
   cout<<endl;
   return 0;
}

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)