The Dutch National Flag problem, which is also simplified as sorting an array containing 0s 1s 2s, is a classic computer science problem proposed by Edsger Dijkstra, a renowned Dutch computer scientist. Dijkstra named the algorithm after the tricolor flag of the Netherlands, which consists of three horizontal stripes in red, white, and blue. This problem is also referred to as “Sort colors” or “Tricolor sorting” and can be related to sorting an array containing only 3 distinct elements.

## Problem Statement

Given an array containing only three distinct elements (or three distinct categories of elements), sort the array in-place such that all occurrences of one element are together, followed by all occurrences of the second element, and then all occurrences of the third element.

**Example input:**

Let’s consider an array of integers containing only `0`

s, `1`

s, and `2`

s:

```
[1, 0, 2, 1, 0, 1, 2, 2, 0, 1]
```

**Expected output:**

```
[0, 0, 0, 1, 1, 1, 1, 2, 2, 2]
```

In this sorted output, all `0`

s come first, followed by all `1`

s, and then all `2`

s.

## Relation With Dutch National Flag

The problem of sorting an array containing only `0`

s, `1`

s, and `2`

s is often referred to as the “Dutch National Flag” problem due to its connection with the colors of the Dutch flag. It consists of three horizontal stripes: red at the top, white in the middle, and blue at the bottom. Below is how the dutch national flag looks:

If we associate 0 with red, 1 with white, and 2 with blue, the problem of sorting these numbers becomes analogous to arranging the colors of the Dutch flag in the correct order. Just as the Dutch flag has distinct sections for each color, the sorting algorithm aims to create three distinct sections in the array: one for `0`

s, one for `1`

s, and one for `2`

s. Below is how the example array looks after coloring:

## Solving with Sorting Algorithms

We can use any standard sorting algorithms such as Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, or Quick Sort to group and move all `0`

s to the beginning, followed by all `1`

s and then all `2`

s. However, it’s important to note that while these methods will work, they are not specifically optimized for this particular problem.

The time complexity of these standard sorting algorithms varies depending on the chosen method. For instance, simpler algorithms like Bubble Sort, Insertion Sort, and Selection Sort typically have a time complexity of `O(n^2)`

, where `n`

is the number of elements in the array. More efficient algorithms like Merge Sort and Quick Sort offer better performance with a time complexity of `O(n log n)`

. Similarly, the space complexity differs among these algorithms, ranging from `O(1)`

for in-place sorting methods to `O(n)`

for algorithms that require additional memory proportional to the input size. While these general-purpose sorting algorithms will get the job done, there are more efficient approaches specifically tailored to sorting arrays containing elements of only 3 distinct values.

Click here to learn more about different sorting techniques

## Counting Approach (Two Pass Solution)

The main idea behind the Counting Approach for sorting `0`

s, `1`

s, and `2`

s is to count the occurrences of each number in the array, then use that information to reconstruct the sorted array. This method is faster than traditional sorting algorithms for this specific case, as it only requires two passes through the array.

Below is the algorithm:

- Initialize three variables:
`zeroes_count`

,`ones_count`

, and`twos_count`

to keep track of the number of`0`

s,`1`

s, and`2`

s in the array. - Traverse the entire array once, incrementing the appropriate count variable for each element encountered.
- Reset a pointer to the beginning of the array.
- Fill the first
`zeroes_count`

positions of the array with`0`

s. - Fill the next
`ones_count`

positions of the array with`1`

s. - Fill the remaining
`twos_count`

positions of the array with`2`

s. - The array is now sorted with all
`0`

s at the beginning, followed by all`1`

s, and then all`2`

s at the end.

This approach is highly efficient, with a time complexity of O(n) and a space complexity of O(1). It requires only two passes through the array - one for counting and one for filling. This makes it faster than traditional sorting algorithms for this specific case.

However, it’s important to note that this method has limitations. It only works for sorting a fixed set of distinct values (in this case, `0`

s, `1`

s, and `2`

s). If the array contains unique objects and if sorting needs to be done based on a particular attribute of each object, this approach would not be suitable. In such cases, other sorting algorithms or the algorithm discussed in the next section would be more appropriate.

Implementation for this algorithm is similar to the one for sorting an array with `0`

s and `1`

s.

## Optimal Solution (3 Pointer Approach)

### Algorithm

Below is a single pass algorithm to sort all elements in the array containing only `0`

s, `1`

s and `2`

s:

- Initialize three pointers:
`low`

: Initially points to the start of the array`mid`

: Initially points to the start of the array`high`

: Initially points to the end of the array

- Use
`mid`

pointer to iterate through the array:- If the element at
`mid`

is`0`

:- Swap it with the element at
`low`

- Move
`low`

and`mid`

pointers one step right

- Swap it with the element at
- If the element at
`mid`

is`1`

:- Leave it as is
- Move
`mid`

pointer one step right

- If the element at
`mid`

is 2:- Swap it with the element at
`mid`

- Move
`high`

pointer one step left - Don’t move
`mid`

pointer (we need to check the swapped element)

- Swap it with the element at

- If the element at
- Repeat step 2 until
`mid`

pointer crosses`high`

pointer - The array is now sorted with all
`0`

s at the beginning, all`1`

s in the middle, and all`2`

s at the end.

The idea behind this algorithm is to use `mid`

pointer to traverse the array and `low`

pointer is used to indicate the position until which all the elements are `0`

s and `high`

pointer is used to indicate the position from which all the elements are `2`

s until the end of array. Each time the `mid`

pointer encounters `0`

, it moves it towards left and each time the `mid`

pointer encounters `2`

, it moves it towards right.

This algorithm efficiently sorts an array containing only `0`

s, `1`

s, and `2`

s in a single pass, making it faster than traditional sorting methods for this specific scenario.

### Step by Step Visualization

Below are the slides which visually walk you through the entire algorithm step by step:

### Implementation

```
def dutch_national_flag(arr):
# Initialize the three pointers
low = 0
mid = 0
high = len(arr) - 1
# Iterate through the array using the mid pointer
while mid <= high:
if arr[mid] == 0:
# If the element at mid is 0,
# swap it with the element at low
arr[low], arr[mid] = arr[mid], arr[low]
# Move both low and mid pointers to the right
low += 1
mid += 1
elif arr[mid] == 1:
# If the element at mid is 1,
# leave it as is and move mid pointer
mid += 1
else: # arr[mid] == 2
# If the element at mid is 2,
# swap it with the element at high
arr[mid], arr[high] = arr[high], arr[mid]
# Move high pointer to the left (backwards)
high -= 1
# Don't move mid pointer here as we need to check the swapped element
# Input array
input_array = [1, 0, 2, 1, 0, 1, 2, 2, 0, 1]
print("Input array:", input_array)
# Run the function which sorts the array in place
dutch_national_flag(input_array)
print("Sorted array:", input_array)
```

### Time and Space Complexity Analysis

**Time Complexity**: `O(n)`

The algorithm performs a single pass through the array and examines each element exactly once and performs at most one swap operation per element. Since the number of operations is directly proportional to the input size, the time complexity is linear, `O(n)`

.

**Space Complexity**: `O(1)`

This algorithm sorts the array in-place, meaning it doesn’t require any extra space that grows with the input size. It only uses a constant amount of extra space for the three pointers (`low`

, `mid`

, and `high`

) and a few temporary variables for swapping. Therefore, the space complexity is constant, `O(1)`

.

## Further Reading

Although the Dutch National Flag problem statement involves sorting an array with 3 distinct values, algorithms used to solve the problem can also be used for Three-way partitioning of an array with minor modifications. For example, consider the array shown below:

```
[4, 2, 7, 1, 5, 3, 6]
```

If we need to partition the array into 3 segments such that:

- First segment containing elements less than the pivot
- Second segment containing elements equal to the pivot
- Third segment containing elements greater than the pivot,

We can apply the 3 pointer approach to solve the problem of three way partitioning by thinking of all elements less than the pivot element as `0`

s, all elements equal to the pivot element as `1`

s and all elements greater than the pivot element as `2`

s. After applying this algorithm to our example array with `4`

as the pivot element, we would end up with the below array:

```
[2, 1, 3, 4, 5, 7, 6]
```

In this result, all elements less than `4`

are on the left, the pivot (`4`

) is in the middle, and all elements greater than `4`

are on the right. This is useful in various sorting and searching algorithms, such as quicksort with three-way partitioning.