What is the Dutch National Flag problem?

The Dutch National Flag problem is a computer science programming problem created by Edsger Dijkstra. The task is to sort an array of elements into three groups (e.g., 0s, 1s, and 2s) in a single pass. The name comes from the three colors of the Dutch flag.

How does the algorithm work?

It uses three pointers: a low pointer for the '0' section, a high pointer for the '2' section, and a mid pointer that iterates through the array. Elements are swapped based on their value relative to the pivot (1), partitioning the array into three sections.

Array Sorting

Dutch National Flag Algorithm

An efficient, in-place sorting algorithm for arrays with three distinct values. This single-pass approach is a common interview question.

Sort Colors (0s, 1s, and 2s)

This implementation sorts an array containing only 0s, 1s, and 2s using the three-pointer Dutch National Flag approach.

                            function sortColors(nums) {
                            let low = 0, mid = 0, high = nums.length - 1;
                            
                            while (mid <= high) {
                            if (nums[mid] === 0) {
                            [nums[low++], nums[mid++]] = [nums[mid], nums[low]];
                            } else if (nums[mid] === 1) {
                            mid++;
                            } else {
                            [nums[mid], nums[high--]] = [nums[high], nums[mid]];
                            }
                            }
                            }
                        

AI Coach Hint: The key is the invariant: all elements before `low` are 0s, all elements between `low` and `mid` are 1s, and all elements after `high` are 2s. The loop continues until `mid` crosses `high`, processing the unknown region.