medium Dutch National Flag Problem

Problem Statement

Given an array containing 0s, 1s and 2s, sort the array in-place. You should treat numbers of the array as objects, hence, we can’t count 0s, 1s, and 2s to recreate the array.

The flag of the Netherlands consists of three colors: red, white and blue; and since our input array also consists of three different numbers that is why it is called Dutch National Flag problem.

Examples

Example 1

Input: arr = [1, 0, 2, 1, 0]
Output: [0, 0, 1, 1, 2]
Explanation:
- All 0s are moved to the front, 1s in the middle, and 2s at the end.
- The relative order within each group doesn't matter.

Example 2

Input: arr= [2, 2, 0, 1, 2, 0]
Output: [0, 0, 1, 2, 2, 2]
Explanation:
- All 0s come first, followed by the 1, and then all 2s at the end.
- Sorting is done in-place without using extra space or counting.

Constraints:

n == arr.length
1 <= n <= 300
arr[i] is either 0, 1, or 2.

Try it yourself

Try solving this question here:

✅ Solution Dutch National Flag Problem

Problem Statement

Given an array containing 0s, 1s and 2s, sort the array in-place. You should treat numbers of the array as objects, hence, we can’t count 0s, 1s, and 2s to recreate the array.

The flag of the Netherlands consists of three colors: red, white and blue; and since our input array also consists of three different numbers that is why it is called Dutch National Flag problem.

Examples

Example 1

Input: arr = [1, 0, 2, 1, 0]
Output: [0, 0, 1, 1, 2]
Explanation:
- All 0s are moved to the front, 1s in the middle, and 2s at the end.
- The relative order within each group doesn't matter.

Example 2

Input: arr= [2, 2, 0, 1, 2, 0]
Output: [0, 0, 1, 2, 2, 2]
Explanation:
- All 0s come first, followed by the 1, and then all 2s at the end.
- Sorting is done in-place without using extra space or counting.

Constraints:

n == arr.length
1 <= n <= 300
arr[i] is either 0, 1, or 2.

Solution

The brute force solution will be to use an in-place sorting algorithm like Heapsort which will take . Can we do better than this? Is it possible to sort the array in one iteration?

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. In the end, all 0s are on the left, all 1s are in the middle, and all 2s are on the right.

Step-by-Step Algorithm

We start by initializing three variables: low to 0, high to the last index of the array, and i also to 0. Low is meant to keep track of the latest position where a 0 should be placed, high is meant to keep track of the latest position where a 2 should be placed, and i is used to iterate through the array.
We then start a loop that continues as long as i is less than or equal to high. In each iteration of the loop, we check the value of the array at the index i.
If the value is 0, we swap the values at the indices i and low. We then increment both i and low, since we know that the new element at low is 0 (sorted in its correct place) and we can move to the next index.
If the value is 1, we do nothing other than increment i. This is because we want 1s to be in the middle of the array.
If the value is 2, we swap the values at i and high. However, after the swap, we only decrement high without incrementing i. This is because the new value at index i (after the swap) could be 0, 1 or 2, and we need to check this value again in the next iteration.
The swap function simply switches the values at two given indices in the array.
The process continues until i is greater than high, at which point every element in the array has been checked and placed in its correct position. Hence, the array is now sorted.

Algorithm Walkthrough

Initial State:

Array: [1, 0, 2, 1, 0]
low = 0, high = 4
i = 0

Step-by-Step Walkthrough:

First Iteration (i = 0):
- arr[i] = 1
- Since it's 1, just increment i.
- State after iteration:
  - Array: [1, 0, 2, 1, 0]
  - low = 0, high = 4
  - i = 1
Second Iteration (i = 1):
- arr[i] = 0
- Swap arr[i] with arr[low] (Swap positions 1 and 0).
- Increment low and i.
- State after iteration:
  - Array: [0, 1, 2, 1, 0]
  - low = 1, high = 4
  - i = 2
Third Iteration (i = 2):
- arr[i] = 2
- Swap arr[i] with arr[high] (Swap positions 2 and 4).
- Decrement high.
- i remains the same to check the swapped element.
- State after iteration:
  - Array: [0, 1, 0, 1, 2]
  - low = 1, high = 3
  - i = 2
Fourth Iteration (i = 2):
- arr[i] = 0
- Swap arr[i] with arr[low] (Swap positions 2 and 1).
- Increment low and i.
- State after iteration:
  - Array: [0, 0, 1, 1, 2]
  - low = 2, high = 3
  - i = 3
Fifth Iteration (i = 3):
- arr[i] = 1
- Since it's 1, just increment i.
- State after iteration:
  - Array: [0, 0, 1, 1, 2]
  - low = 2, high = 3
  - i = 4

Final State:

Array: [0, 0, 1, 1, 2]
All 0s are at the beginning, followed by all 1s, and all 2s at the end.

Code

Here is what our algorithm will look like:

java

class Solution {

  public int[] sort(int[] arr) {
    // all elements < low are 0 and all elements > high are 2
    // all elements from >= low < i are 1
    int low = 0, high = arr.length - 1;
    for (int i = 0; i <= high;) {
      if (arr[i] == 0) {
        swap(arr, i, low);
        // increment 'i' and 'low'
        i++;
        low++;
      } else if (arr[i] == 1) {
        i++;
      } else { // the case for arr[i] == 2
        swap(arr, i, high);
        // decrement 'high' only, after the swap the number at index 'i' could be 0, 1,
        //  or 2
        high--;
      }
    }
    return arr;
  }

  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    int[] arr = new int[] { 1, 0, 2, 1, 0 };
    arr = sol.sort(arr);
    for (int num : arr) System.out.print(num + " ");
    System.out.println();

    arr = new int[] { 2, 2, 0, 1, 2, 0 };
    arr = sol.sort(arr);
    for (int num : arr) System.out.print(num + " ");
  }
}

Complexity Analysis

Time Complexity

Single pass through the array: The algorithm uses a single for loop that iterates through the array once. The pointer i moves from the start to the end of the array, and at each iteration, it processes the current element.
Swaps: Each swap operation occurs in constant time . Since each element is either swapped or incremented only once, the number of swaps and comparisons is proportional to the length of the array.

Overall time complexity: Since the algorithm processes each element of the array exactly once, the time complexity is , where N is the number of elements in the array.

Space Complexity

In-place modification: The algorithm sorts the array in place, meaning that it doesn't require any additional space that scales with the size of the input array.
Auxiliary space: The only extra space used is for a few integer variables (low, high, and i), which require constant space, .

Overall space complexity: Since the algorithm does not use any additional data structures, the space complexity is .

🤖 Don't fully get this? Learn it with Claude

Stuck on Dutch National Flag Problem? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Dutch National Flag Problem** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Dutch National Flag Problem** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Dutch National Flag Problem**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Dutch National Flag Problem**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Pair with Target Sum Comparing Strings containing Backs →