## Dutch National Flag Problem

We’ll cover the following.

• Problem Statement
• Intuition
• Solution
• Code
• Time Complexity
• Space Complexity

### Problem Statement

Given an array containing only 0s, 1s and 2s, sort the array in place. Note that you should treat the numbers as objects, hence we can’t count 0s, 1s and 2s to recreate the array. Also you are not supposed to use the library’s sort function for this problem.

#### Example 1

Input : 1 0 2 1 0

Output : 0 0 1 1 2

#### Example 2

Input : 2 2 0 1 2 0

Output : 0 0 1 2 2 2

#### Intuition:

The problem requires tracking the positions of 3 numbers only i.e the 0s, 1s and 2s. So we can track the smallest number(in this case 0) using one pointer and the greatest number using another pointer(in this case 2). So we can proceed with the two pointer technique.

#### Solution

We can use a Two Pointers approach while iterating through the array. Letâ€™s say the two pointers are called `low` and `high` which are pointing to the first and the last element of the array respectively. So while iterating, we will move all 0s before `low` and all 2s after `high` so that in the end, all 1s will be between `low` and `high`.

#### Time Complexity:

The time complexity of the above algorithm will be O(N) as we are iterating the input array only once.

#### Space Complexity:

The algorithm runs in constant space O(1) as we are not using any auxiliary space proportional to our input size.