Sort an Array of 0s, 1s, and 2s Using Dutch National Flag Algorithm

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

You are given an array consisting of only the numbers 0, 1, and 2. Your task is to sort the array in-place so that all 0s come first, then all 1s, followed by all 2s.

This problem must be solved without using any sorting function and in a way that is both time and space efficient. You should not use extra space for counting or storing elements separately.

Return the same array after sorting.

Examples❯

Input Array Sorted Output Description
[0, 2, 1, 2, 0] [0, 0, 1, 2, 2] Mixed 0s, 1s, 2s in random order
[2, 2, 1, 1, 0, 0] [0, 0, 1, 1, 2, 2] Completely reversed input
[0, 0, 0] [0, 0, 0] All elements are the same (0s)
[1, 1, 1, 1] [1, 1, 1, 1] All 1s – already sorted
[2, 2, 2] [2, 2, 2] All elements are 2s
[0, 1, 2] [0, 1, 2] Already sorted input
[1, 0, 2] [0, 1, 2] Just one swap needed
[] [] Empty input – nothing to sort
[2] [2] Single element array – valid and sorted
[2, 0] [0, 2] Only two elements in reverse

Solution❯

Understanding the Problem

We are given an array that only contains the numbers 0, 1, and 2. Our goal is to sort this array in-place so that all 0s come first, followed by all 1s, and then all 2s. This problem is also known as the Dutch National Flag problem.

Since we know the array only has 0s, 1s, and 2s, we can solve this more efficiently than using general sorting algorithms like quicksort. We’ll walk through this step-by-step using an intuitive approach designed for beginners.

Step-by-Step Approach with Example

Let’s say the input array is:

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

We will use a three-pointer technique:

  • low: Points to the position where the next 0 should go.
  • mid: Points to the current element we are checking.
  • high: Points to the position where the next 2 should go.

Initial State


low = 0, mid = 0, high = 5
Array: [2, 0, 2, 1, 1, 0]

Case 1: arr[mid] == 0

This value should go to the beginning. We swap arr[mid] with arr[low] and move both low and mid one step forward.

Case 2: arr[mid] == 1

1 is already in the middle section where it belongs, so we just move mid forward.

Case 3: arr[mid] == 2

We want to move 2 to the end. We swap arr[mid] with arr[high] and move high backward. But we do not move mid yet, because we need to check the new element that was swapped in.

Full Walkthrough of the Example

Let’s see how the array evolves:

  1. Start: [2, 0, 2, 1, 1, 0]
  2. Swap arr[0] and arr[5] → [0, 0, 2, 1, 1, 2], low = 0, mid = 0, high = 4
  3. arr[0] == 0 → swap arr[0] and arr[0], move low and mid → [0, 0, 2, 1, 1, 2]
  4. arr[1] == 0 → swap arr[1] and arr[1], move low and mid → [0, 0, 2, 1, 1, 2]
  5. arr[2] == 2 → swap arr[2] and arr[4] → [0, 0, 1, 1, 2, 2], high = 3
  6. arr[2] == 1 → just move mid → [0, 0, 1, 1, 2, 2]
  7. arr[3] == 1 → just move mid → done

Final result: [0, 0, 1, 1, 2, 2]

Handling Edge Cases

  • Empty array: No elements to process — the loop doesn’t run, so we return the array as-is.
  • Single element: One value is already "sorted" — return it directly.
  • All values are the same: For example, all 0s or all 2s — no swaps needed, array remains unchanged.

Why This Algorithm Is Efficient

Because we only go through the array once — and every swap or comparison brings us closer to the goal — this method runs in O(n) time and uses O(1) space.

It’s fast, space-efficient, and easy to implement once the logic is clear!

Algorithm Steps❯

  1. Given an array arr consisting only of 0s, 1s, and 2s.
  2. Initialize three pointers: low = 0, mid = 0, and high = n - 1.
  3. Traverse the array with mid pointer until it exceeds high:
  4. → If arr[mid] == 0, swap arr[low] and arr[mid], increment both low and mid.
  5. → If arr[mid] == 1, just move mid one step ahead.
  6. → If arr[mid] == 2, swap arr[mid] and arr[high], and decrement high.
  7. Continue until the array is sorted.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

void sortColors(int arr[], int n) {
    int low = 0, mid = 0, high = n - 1;
    while (mid <= high) {
        if (arr[mid] == 0) {
            int temp = arr[low];
            arr[low] = arr[mid];
            arr[mid] = temp;
            low++;
            mid++;
        } else if (arr[mid] == 1) {
            mid++;
        } else {
            int temp = arr[mid];
            arr[mid] = arr[high];
            arr[high] = temp;
            high--;
        }
    }
}

int main() {
    int arr[] = {2, 0, 2, 1, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    sortColors(arr, n);
    printf("Sorted Array: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)In all cases, the array is traversed only once from start to end using the mid pointer.
Average CaseO(n)Each element is visited at most once, making the number of operations directly proportional to the array size.
Worst CaseO(n)Even in the worst distribution (e.g., alternating 0s and 2s), the algorithm completes in linear time as each element is handled in a single pass.

Space Complexity❯

O(1)

Explanation: The algorithm uses only constant extra space with three pointers (low, mid, high), and all operations are done in-place.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...