DEV Community

Manoj Kumar
Manoj Kumar

Posted on

Sort 0s, 1s and 2s – Python (Dutch National Flag Algorithm)

#python #beginners

🎯 Sort 0s, 1s and 2s – Python (Dutch National Flag Algorithm)

Hi All,

Today I solved an important problem: Sorting an array containing only 0s, 1s, and 2s without using built-in sort.

📌 Problem Statement

Given an array arr[] containing only:

  • 0s
  • 1s
  • 2s

Sort the array in ascending order.

⚠️ Constraints:

  • Do NOT use built-in sorting
  • Must solve in O(n) time and O(1) space

🔍 Examples

Example 1: 

arr = [0, 1, 2, 0, 1, 2]
Enter fullscreen mode Exit fullscreen mode

Output: 

[0, 0, 1, 1, 2, 2]
Enter fullscreen mode Exit fullscreen mode

Example 2: 

arr = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]
Enter fullscreen mode Exit fullscreen mode

Output: 

[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2]
Enter fullscreen mode Exit fullscreen mode

💡 Approach

🔹 Method: Dutch National Flag Algorithm (Optimal)

👉 Use three pointers:

  • low → for 0s
  • mid → current element
  • high → for 2s

🧠 Logic

  • If element is 0 → swap with low, move both pointers
  • If element is 1 → move mid
  • If element is 2 → swap with high, move high

💻 Python Code 

def sort012(arr):
    low = 0
    mid = 0
    high = len(arr) - 1

    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1

        elif arr[mid] == 1:
            mid += 1

        else:  # arr[mid] == 2
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1

    return arr
Enter fullscreen mode Exit fullscreen mode

🔍 Dry Run

For:

arr = [2, 0, 1]
Enter fullscreen mode Exit fullscreen mode

Steps:

  • Swap 2 with high → [1, 0, 2]
  • mid moves → swap 1 (no change)
  • Swap 0 with low → [0, 1, 2]

Final Output:

[0, 1, 2]
Enter fullscreen mode Exit fullscreen mode

🖥️ Sample Output 

Input: [0, 1, 2, 0, 1, 2]
Output: [0, 0, 1, 1, 2, 2]

Input: [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]
Output: [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2]
Enter fullscreen mode Exit fullscreen mode

⚡ Complexity Analysis

  • Time Complexity: O(n) ✅ (single pass)
  • Space Complexity: O(1) ✅ (no extra space)

🧠 Why this is important?

  • Avoids sorting (O(n log n))
  • Uses efficient in-place algorithm
  • Very common in coding interviews

✅ Conclusion

This problem helped me understand:

  • Two pointer / multi-pointer technique
  • In-place sorting
  • Optimized problem-solving

🚀 This is a must-know problem for interviews!

Top comments (0)