Member-only story
Dutch National Flag Algorithm
Having fun with Leetcode! ❤️❤️🤍🤍💙💙
Some algorithms are easy to copy and surprisingly difficult to explain.
The Dutch National Flag algorithm fits into a short Python function. Yet one line often causes confusion: after moving a 2 to the end, we do not advance the pointer that scans the list.
Why?
To answer that, we need to track what we know about each part of the list. Once those regions are clear, the pointer movements follow naturally.
The problem: three values, three groups
Suppose we have this Python list:
nums = [1, 2, 0, 1, 2, 0]We want to rearrange it into:
[0, 0, 1, 1, 2, 2]The requirements are simple: modify the existing list, use constant extra space, and finish in linear time.
This is the setting of LeetCode 75: Sort Colors, where 0, 1, and 2 represent red, white, and blue. Its follow-up asks for a one-pass solution with constant extra space.
The name refers to arranging the three colors of the Dutch flag. Edsger W. Dijkstra popularized this partitioning problem; Princeton’s Algorithms material describes its connection to three-way partitioning.
Here, we will work directly with Python lists. Our “pointers” are simply integer indices.
