C++ solution in 8 lines: an instance of the Dutch national flag problem by Edsger Dijkstra

  • 20

    A more general problem is the Dutch national flag problem by Edsger Dijkstra, which can be used to solve this problem, as well as partition in quicksort.

    class Solution {
        void sortColors(int A[], int n) {
            int i = 0, lo = 0, hi = n - 1;
            // invariants: A[0..lo-1] are less than pivot 1, A[lo..i-1] equal, A[hi+1..end] greater
            while (i <= hi)
                if (A[i] < 1)
                    swap(A[i++], A[lo++]);
                else if (A[i] > 1)
                    swap(A[i], A[hi--]);

  • 0

    great, but even reading i feel it's easy making mistakes when deciding i++, lo++, hi--

  • 0

    That's where the advantage of invariant shows up: you just have to ensure the invariant still holds after each iteration. Try it on a piece of paper.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.