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

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

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

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

• perfect algorithm! still takes time to think tho short

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

• This post is deleted!

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