Leetcode 75: Sort Colors

Dutch National Flag

You are given an array nums with some N number of objects which are colored red, white or blue. Your task is to sort the array (in-place) such that same color objects are adjacent and with the colors in the order Red, White, Blue.

Here Red, Blue and White are represented by integers 0, 1, and 2 respectively. Your task is to solve the problem in Linear Time and without using any in-built library sort function.

Naive Approach

Although it is mentioned that we have to solve the question in linear time complexity O(N), but if you encountered this question in an Online Assessment and you can’t really figure out the DNFS Algorithm, the you can just simply use Quick Sort or Merge Sort, that will take O(NlogN) time complexity.

Better Approach

Counting Sort, since there are only 3 unique number of elements that are there in the array, we can just simply keep track of the frequencies of each of the unique element and then just re-iterate over the array again to replace the values according to the frequencies of 0s, 1s, and 2s. This approach will take linear time complexity O(2N), but still we are using two for loops, first to count the frequencies and the second to replace the elements according to the frequencies.

void sortColors (vector<int>& nums) {
  // Time Complexity: O(2N)
  // Space Complexity: O(1)
  
  int zeroes = 0;
  int ones = 0;
  int twos = 0;
  
  for (int value : nums) {
    if (value == 0) zeroes++;
    else if (value == 1) ones++;
    else twos++;
  }
  
  int n = nums.size();
  for (int i = 0; i<n; i++) {
    if (zeroes) {
      nums[i] = 0;
      zeroes--;
    }
    else if (ones) {
      nums[i] = 1;
      ones--;
    }
    else {
      nums[i] = 2;
      twos--;
    }
  }
}

Optimal Approach

Well, you might have noticed the flag above, that is the Dutch’s National Flag, and the algorithm that we will be using to solve this question optimally is name after the flag, it is Dutch National Flag Sorting Algorithm. It was created by the renowned scientist Edsger W. Dijkstra in 1976.

Get Rohit Saini’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

To implement this algorithm, we will be needing three pointers: low, medium and high pointing at 0, 0, and n — 1 respectively.

The idea is pretty simple, you just have to follow the below steps on each iteration:

1. All 0s lies from [0, low — 1] index both inclusive
2. All 1s lies from [low, mid — 1] index both inclusive
3. All 2s lies from [high + 1, n — 1] index both inclusive
4. Rest all the undiscovered elements lies from [mid, high]

Operations that you need to perform depending on the value at the mid pointer:

1. If value is 0, swap value of low with mid and move both low and mid by one place.
2. If value is 1, don’t move low, just move mid one place ahead
3. If value is 2, swap value of high and mid, and move ONLY high one place back.

void sortColors(vector<int>& nums) {
  // Dutch National Flag Sorting Algorithm
  // Time complexity: O(N)
  // Space complexity: O(1)
        
  int n = nums.size();
  int low = 0;
  int mid = 0;
  int high = n - 1;

  while (mid <= high) {
    if (nums[mid] == 1) mid++;
    else if (nums[mid] == 0) {
      swap(nums[low], nums[mid]);
      low++;
      mid++;
     }
    else {
      swap(nums[mid], nums[high]);
      high--;
    }
  }   
}

Note that we are going till the mid and high are ( ≤ )to each other, but why not ( < ) only, since unprocessed values lies from mid to high (both inclusive) that’s why we are running the loop till ( ≤ ) in order to process every single unprocessed element from mid to high.

I hope whatever characters I dumped here made sense and if it did then make sure to like the story. Also if you find any syntax error or any other error in general please feel free to reach out.