Sort an array of 0’s, 1’s and 2’s

You are given an array whose elements are only 0’s, 1’s and 2’s. You need to sort the array in increasing order in linear time complexity without using extra space in a single iteration.

Sample Input: {0, 1, 2, 0, 1, 2, 1, 0, 0}
Expected Output: {0, 0, 0, 0, 1, 1, 1, 2, 2}

Algorithm:

We can use the Dutch National Flag algorithm here. It uses a 3 pointer approach to sort the array.

  1. Initialize 3 pointers low = 0, middle = 0, high = N – 1 , where N is the size of the array.
  2. Iterate while middle <= high and do the following,
    If the arr [middle] = 0, we swap arr [middle] with arr [low] and increment middle and low pointers by 1. We do this because, we need to put the 0’s before 1’s and middle pointer should point at 1 and low pointer should point at 0.
    If arr [middle] = 1, we just increment the middle pointer by 1.
    If arr [middle] = 2, we swap arr [middle] with arr [high] and decrement high pointer by 1.
#include <bits/stdc++.h>
using namespace std;

void helper(vector<int> &nums, int n){
	int l=0, m=0, h=n-1;
	while(m<=h){
		if(nums[m]==0){
			swap(nums[m], nums[l]);
			m++;
			l++;
		}
		else if(nums[m]==1){
			m++;
		}
		else if(nums[m]==2){
			swap(nums[m], nums[h]);
			h--;
		}
	}
}

int main(){
	vector<int> nums = {0, 1, 2, 0, 1, 2, 1, 0, 0};
	helper(nums, nums.size());
	for(auto i:nums){
		cout<<i<<" ";
	}
	return 0;
}

Check out Top 20 most asked Dynamic Programming questions.

One comment

Leave a Reply

Your email address will not be published.