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


  • 68
    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.


  • 5
    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.


  • 3
    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;
                }
            }
        }
    

  • 0
    S

    perfect algorithm! still takes time to think tho short


  • 0
    L

    Your algorithm won't work in real world. Color is just the key of object. Swap is necessary.


Log in to reply
 

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