Mark As Completed Discussion

This problem is a variant of the quick sort algorithm, so we know we'll need to do some form of partitioning. Partitioning is the act of splitting an array up into sub-arrays, "according to whether they are less than or greater than" a pivot number.

At first glance, it seems like an impossible task: how can we determine where an element should go without being aware of its relative positioning compared with the rest of the elements?

There's one way-- by using multiple pointers.

The idea behind the final dutch national flag algorithm is to use three pointers, low, mid, and high. We start with low and mid initialized to 0, and our goal is to expand these "groups" (the sub-array from one of these indices to the next) over time. We'll do this via a series of swaps.

Don't worry, we'll break this down more as we go.