We can also use bucket sorting in this problem. In bucket sorting, there must be a limited number of known elements in the array. This is exactly the case in this problem. We only have 3 values (0, 1, and 2).

So to apply bucket sort, we create a list of buckets (counts) and count all the elements in the array to their corresponding buckets. Then, we do the in-place placement of the number of elements in the array and return it. See the solution code below. This is actually simpler than quicksort, as we do not need to keep track of three pointers.

Similar to the algorithm above, we are just passing through the array twice only. So the complexity of the below code will also be O(2n) = O(n). Again, we are only allocating a number of variables. Keep in mind that counts array is a very small fixed-sized (3) array. So it won't make the memory complexity linear. The space complexity of this algorithm would be O(1).

xxxxxxxxxx

def dutch_national_flag(arr):

    counts = [0, 0, 0]

    for i in arr:

        counts[i] += 1

    i = 0

    for val, count in enumerate(counts):

        for _ in range(count):

            arr[i] = val

            i += 1

​

    return arr