Dutch national flag algorithm

2 min read

Problem


The flag of the Netherlands consists of three colours: red, white, and blue. Given an array of three colors arranged randomly, the task is to arrange them such that:

  • Elements of the same colour are adjacent.
  • Their collective colour groups are in the correct order (red, white, blue).

Algorithm

The optimal solution for the problem is propsed by Edsger Dijkstra. The solution uses three pointers (red, white, blue) for each colours, and keeps four invariants:

  • Everything at the left of red are red.
  • From the red pointer to the left of the white pointer are white.
  • From the white pointer to the blue pointer are unknown.
  • Everything at the right of blue are blue.

dutch-national-flag-pointers-example

The algorithm starts by setting pointers red and white to the first element, and blue pointer to the last element.

Its time complexity is , where is the number of elements. Its space complexity is , as it only needs the space for pointers.

Below is a python code of the Dutch national flag algorithm, that sorts the given array in place.

def dutch_national_flag(arr: List[int]) -> None:
    red, white, blue = 0, 0, len(arr) - 1
 
    while white <= blue:
        match arr[white]:
            case RED:
                arr[red], arr[white] = arr[white], arr[red]
                red += 1
                white += 1
            case WHITE:
                white += 1
            case BLUE:
                arr[blue], arr[white] = arr[white], arr[blue]
                blue -= 1

References

Graph View

Graph View