The 'Dutch Flag' Quick Sort

Is it weird to have a favorite algorithm? I definitely have a top four. Maybe it's because they remind me of puzzles I loved solving as a kid -- when I was growing up, my dad never let us get a Nintendo. Instead, I grew up solving logic puzzles in my spare time. And... I still love them. I think that's why I loved the data structures and algorithms prep in my bootcamp and why I've enjoyed studying for technical interviews.

Over the next few weeks, I'll be sharing my favorite data structures and algorithms problems that I've worked with. Starting with... quick sorting by a pivot point, AKA the Dutch flag problem.

^{Image credit: Unsplash}

So what's the big problem?

The Dutch Flag problem comes to us from the 1970's thanks to in his book, A Discipline of Programming Edsger Dijkstra.

The problem is usually presented in some form of the following:

Given an array of 0s, 1s, and 2s, sort the items in-place in ascending order.

^{leetcode.com uses a color sort scenario to present this}

To me, the solution for this is a beautiful sort of "controlled chaos". Once we get started, items in our array move all over the place, but thanks to some thoughtful pointers, we complete this problem in one fell swoop through the data.

Why would I use this solution?

Some quicksort algorithms can take up to O(N^2) runtime if there are a large number of repeated items like we have here. The algorithm outlined below works with any integer range input so long as a pivot point is given (for example an array with integers between 0-7 and a pivot point of, say, 3 could be sorted in this same way). The only difference would be a tweak to the if statements, and the inclusion of an additional argument (the pivot). The method I outline below solves this problem in O(N) runtime, and 0(1), or constant, space.

Let's go!

1. Initialize Variables

This solution depends on the use of three pointers. We'll start by initializing two of them -- a high pointer and a low pointer -- as the last and first items in our array respectively. The third we'll initialize as i -- this is where we will track what item we are evaluating.

The high and low will track what space we should swap a high or low value to. So essentially "low" is one index AFTER the last 0 we've placed so far, and "high" is one index BEFORE the last 2 we've placed so far. And... since we haven't placed ANY yet, they are at the exact beginning and end of our array.

Javascript

sortColors = (nums) => {
  let low = 0;
  let high = nums.length-1;
  let i = 0; 

};

Python

class Solution(object):
    def sortColors(self, nums):
        high = len(nums)-1
        low = 0
        i = 0

2. Set up our loop syntax

Now, we know we need to visit each item to evaluate it. That means we'll need a loop. For this problem, we'll run a while loop while i <= high. Why do we only need to run it while i <= high? Well, because we know that everything PAST high has already been sorted into place. We KNOW they are 2's. Therefore, there's no need to evaluate them a second time.

Since we know we're returning an updated version of the same array, we'll throw our return statement in there now, too.

Javascript

sortColors = (nums) => {
  let low = 0;
  let high = nums.length-1;
  let i = 0; 

while (i <= high) {
  if(nums[i] === 0){

  } else if (nums[i] === 2){

  } else {

  }
}
return nums;   

};

Python

class Solution(object):
    def sortColors(self, nums):
        high = len(nums)-1
        low = 0
        i = 0

        while i<= high:
            if nums[i] == 0:

            elif nums[i] == 2:

            else:

        print nums

3. Getting down to business -- swapping items

Now that we're all set up, let's work through what will happen at each item in our array.

If nums[i] is == 0, we will swap the value of nums[i] with nums[low] and increment i AND low. If nums[i]==2, we do the same swap but with [high] and decrement high. However this time we don't increment i. Why is that?

Logically, we know that nums[low] is a 1 (unless we're at index 0). How? Because we know that we must have already evaluated it and decided it didn't need to go anywhere. Therefore, it must be a 1, so we can just increment our i and not worry about it.

However, swapping from nums[high] we have no clue what we're getting really, it's from the end of the array, after i. Therefore, after we swap with nums[high] we do NOT increment i because we need to evaluate whatever just got swapped in there!

Javascript

sortColors = (nums) => {
  let low = 0;
  let high = nums.length-1;
  let i = 0; 

while (i <= high) {
  if(nums[i] === 0){
      [nums[i], nums[low]] = [nums[low], nums[i]];
      low++;
      i++;
  } else if (nums[i] === 2){
      [nums[i], nums[high]] = [nums[high], nums[i]];
      high--;
  } else {
      i++;
  }
}
return nums;   

Python

class Solution(object):
    def sortColors(self, nums):
        high = len(nums)-1
        low = 0
        i = 0

        while i<= high:
            if nums[i] == 0:
                nums[low], nums[i] = nums[i], nums[low]
                i += 1
                low +=1
            elif nums[i] == 2:
                nums[i], nums[high] = nums[high], nums[i]
                high -=1
            elif nums[i] == 1:
                i += 1
        print nums

Here's a brief run through using the sample array from above.

First, we swap the value at i with the value at high and decrement high.

Another 2, so same thing again.

Next are a few ones... We increment i and then at the next item (also a 1) we increment again.

Swap arr[3] with low and increment i and low.

Another 1, so we increment i and then.....

Hopped over arr[4] is a 1 so we increment, then arr[5] is a 2, so it technically swaps with itself, then breaks the loop as i is higher than i.

Hooray! All sorted out!

Now is when you will want to run more tests. Anytime you're working on a problem like this, you'll want to think about what "edge cases" could throw you for a(n infinite) loop.:

• We know our range only contains positive integers, so no need to worry about negatives.
• What if we got an empty array?
• What if our array was all 0's? All 1's? All 2's?
• What if it was already sorted?
• What if it was already sorted in descending order?

I will leave you to check those out on your own.

^{Image credit: Unsplash}

Before I go

As a final note... you can solve all the problems you want, but in the end, a big part of the interview is being able to clearly communicate what is happening in your mind. In my experience talking through my thinking while writing (or typing!) as a teacher, it gets much easier with practice. It becomes second nature eventually. Seriously, I think out loud all day long, for better or for worse. Talk through the problems you're practicing as you solve them. Tell anyone who will listen -- your dog, your cousin, your partner, yourself -- and then tell me how it goes! These skills will not always come easy, but they can come with practice and hard work.

Free resources:

There are so many places to practice and learn about data structures and algorithms! Here are a few free options that I've found helpful:

• Leetcode - Practice problems for data structures and algorithms. Really easy to search by topic or difficulty.
• HackerRank - Another practice problems site. HackerRank tends to give more of a background story for their challenges. Some people love that, others don't. Some employers use their platform to screen candidates.
• Code Signal - This was recommended to me by a mentor. He's used it in the hiring process as a screener. The practice problems are presented in a more gamified way than the sites above.
• Geeks for Geeks - Really great guides for solving problems. They present multiple solutions and outline the runtime for them. It's worth noting most solutions are only given in a limited number of languages, but the logic shared is so valuable.
• YouTube - So many great channels for data structures and algorithms. My top two favorites are Back to Back SWE and Tech Dose.