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


  • 20
    X

    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 {
    public:
        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--]);
                else
                    i++;
        }
    };
    

  • 0
    A

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


  • 0
    X

    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.