Dutch National Flag Problem: In-Place Sorting with Three Pointers

Day 13 of my Python learning journey Today I worked on a classic problem that looks simple, but teaches a very powerful idea. Problem: Sort 0s, 1s, and 2s (Dutch National Flag Problem) Given an array containing only 0, 1, and 2, sort it in-place. Example: arr = [2, 0, 2, 1, 1, 0] Output: [0, 0, 1, 1, 2, 2] What I learned today: Instead of using sorting functions, we can solve this in one pass using pointers. This problem is known as the Dutch National Flag problem. What is Dutch National Flag idea? This concept was given by Edsger Dijkstra. The idea comes from the Dutch flag, which has three colors: Red, White, Blue We map them like this: 0 → Red 1 → White 2 → Blue So the goal is to arrange elements in this order, just like the flag. How the logic works: We divide the array into three parts: Left → all 0s Middle → all 1s Right → all 2s And we maintain three pointers: low → where 0 should go mid → current element high → where 2 should go Code I wrote: arr = [2, 0, 2, 1, 1, 0] 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], arr[high] = arr[high], arr[mid] high -= 1 print(arr) Problems I faced while coding this: At first I tried using sort(), but that defeats the purpose of the problem. I was confused about why we use three pointers instead of two. The condition mid <= high was tricky to understand. I also made mistakes while swapping, which broke the logic. What I finally understood: This algorithm processes each element only once. We don’t need extra space and no nested loops. Time and Space Complexity: Time Complexity: O(n) → single pass through the array Space Complexity: O(1) → in-place sorting Question: Why do we not increase mid when we swap with high? Today’s realization: Some problems are not about coding more, but about thinking in the right structure. #Python #DSA #Coding #Programming #LearningInPublic #100DaysOfCode #PythonProgramming

  • text

To view or add a comment, sign in

Explore content categories