AC Python in place one pass solution O(n) time O(1) space, no swap no count


  • 58
    def sortColors(self, nums):
        i = j = 0
        for k in xrange(len(nums)):
            v = nums[k]
            nums[k] = 2
            if v < 2:
                nums[j] = 1
                j += 1
            if v == 0:
                nums[i] = 0
                i += 1
    
    # 86 / 86 test cases passed.
    # Status: Accepted
    # Runtime: 44 ms
    # 84.03%
    

    Just like the Lomuto partition algorithm usually used in quick sort. We keep a loop invariant that [0,i) [i, j) [j, k) are 0s, 1s and 2s sorted in place for [0,k). Here ")" means exclusive. We don't need to swap because we know the values we want.


  • 4
    T

    A bit of history: this is "Dutch national flag" problem first proposed by Dijkstra.
    https://en.wikipedia.org/wiki/Dutch_national_flag_problem

    Quicksort uses this "3-way partition" to handle input with lots of duplicates.


  • 1
    C

    @dietpepsi nice solution, I took your idea and wrote it in java.

    public void sortColors(int[] nums) {
            for(int i=0,j=0,k=0; k<nums.length; k++){
                int temp = nums[k];
                
                //assigning the current as max
                nums[k] = 2;
                
                // if original is less than 2 then it should be 1
                if(temp < 2){
                    nums[j] = 1;
                    j +=1;
                }
                
                // if original is less than 1 then it should be 0. The above if statement ensures that 1 - index 
                // will always be greater than 0 - index
                if(temp < 1){
                    nums[i] = 0;
                    i += 1;
                }
            }
        }
    

Log in to reply
 

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