Algorithms in Go: Our path to solving the Dutch National Flag problem
Backend Engineer, Aynur Zulkarnaev, shares how his team solved one of the most popular algorithmic patterns, Dutch National Flag.
Most solutions to algorithmic problems can be grouped into a rather small number of patterns. Before we can start to solve some of them, we need to think about how we can classify them. For example, can we apply a fast and slow аlgorithmic pattern or do we need to use a cyclic sort pattern? Some problems can have several solutions based on different patterns. It can easily become quite complex. In this series, we discuss the most popular algorithmic patterns that cover more than 90% of the usual problems we see.
Let’s start by saying that we aren’t going to be talking about the problems from your high school algorithm 101 course. This solution is not intended to cover things like the Karatsuba (fast multiplication) algorithm or prove different methods of sorting.
Instead, we’re going to look at algorithmic patterns focused on practical skills needed for the solution to common problems. For example, when we set up a Prometheus alert for high request latency, we’re dealing with the Sliding Window pattern. Or let’s say we organise a team event and need to find an available time slot for every participant. At the first glance, it’s not so obvious that in doing so, we‘re actually solving an algorithmic problem. In fact, we’re actually solving a bunch of algorithmic problems throughout our daily lives, without even realising it.
That said, it’s the knowledge about algorithmic patterns that helps one to classify a problem and then apply the appropriate method.
Most importantly, understanding algorithmic patterns help to boost general programming skills. It’s especially useful when we need to debug some production code, as it trains us to understand the execution flow.
The Dutch National Flag Problem
The flag of the Netherlands consists of three colours: red, white and blue. Given balls of these three colours arranged randomly in a line (it does not matter how many balls there are), the task is to arrange them such that all balls of the same colour are together and their collective colour groups are in the correct order.
The path to the solution
For simplicity instead of colours red, white, and blue we’ll be dealing with ones, twos and zeroes.
Let’s start by using our own intuition. We have a collection of zeroes, ones and twos. How can we sort it? Well, one option would be to segment by type, putting aside all zeroesinto a bucket, all onesinto another bucket and all twosinto a third. Then, we could fetch and restore all items bucket by bucket, which would leave us with a single organised collection. This approach works perfectly fine and has great performance. It ensures that we touch all the elements both when putting them in and taking them out of the bucket. So, the overall time complexity is O(n) + O(n) ~= O(n). The space complexity is also O(n) as we need to store all items in the buckets.
Great, a solution! But, can we do better than that? While there’s no way to improve our time complexity, there is a more efficient algorithm in regard to space complexity. For this, we need to think about how we’d solve the problem without the additional buckets. Meaning, how we could solve the problem in-place.
Let’s take a leap of faith and pretend that somehow we were able to process a part of the array. We iterate through part of the array and put encountered zeroes and ones at the beginning of the array and twos at the end of the array. Now, we switched to the next index i with some unprocessed value x. What should we do there?
In this case, there are three possibilities: x could be equal to 0, 1 or 2.
Let’s say x is equal to 28. Where should we put it? We already have some twos at the end of the array, so we need to put the current two right before the start of the known twos. We don't know which value is located before the start of the known twos. Let's call this value y.
We swap our current value with y. As we don't know the value y at our current index i, it’s possible that we need to swap it once more. So we don't proceed to the next value. For example, we don't increase our running pointer i. After this operation, we’re left something that looks like this:
As we now have an additionaltwo at the end of the cadence, we need to shift the start of the known twos. This fact tells us that we need to have one more pointer that indicates the start of the processed twos. Let's denote this pointer as high. When we encounter another two, we’ll put it right before this pointer.
Now, let’s consider the case when x is equal to zero. We need to put this zeroright after the last processed zero.
After this operation, we need to shift the end of known zeroes to the right. Therefore, we’ll have another pointer, low, that signifies the end of known zeroes. When we encounter another zero, we’ll place it to the right of this pointer.
We swap the items at indexesi and low+1. As index low+1 goes directly after the index low that denotes the end of zeroes, the value at index low+1 will always be equal to one.
Now, what do we do with ones? That’s a tricky part because, actually, we do nothing. The item is already in place, so we’re free to proceed to the next item.
Ok, this solution could work when we’re in the middle of the processing. But how do we start?
The running pointer starts with a value equal to zero. We don’t have any known twos yet, so the start of twos is equal to the length of the array. In this way, the first encountered two will be put at the very end of the array which seems logical. We don't have any known zeroes either, so the end of zeroes is equal to minus one. Therefore, the first encountered zero will be put at the very beginning of the array and that's exactly what we want.
Right, how do we know where should we stop? We could iterate through the whole array, but at some point the movement becomes redundant. When our running pointer becomes equal to high, we know for sure that the value at that index is equal to two and we have already processed it. Therefore, we can stop there. If we don't have any twos then the value of highis equal to the length of the array, and we stop at the last item.
Finally, we can implement the algorithm in Go:
If you’re interested in working as a Backend Engineer, there’s an open position in my tea (and some more in the company). Prior knowledge of Golang is not required. Keep in mind, I’m not a recruiter, but I can share my personal experience as a Backend Engineer working at SumUp.
Want to read more about algorithmic patterns such as Sliding Window or Iterative Postorder Traversal? Follow Aynur’s series: Algorithms in Go.
