> For the complete documentation index, see [llms.txt](https://quenluo.gitbook.io/leecode-python/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://quenluo.gitbook.io/leecode-python/075.-sort-colors.md).

# 075. Sort Colors

## Question 75

<https://leetcode.com/problems/sort-colors/description/>

Given an array with *n* objects colored red, white or blue, sort them [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

**Note:** You are not suppose to use the library's sort function for this problem.

**Example:**

```
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
```

### Answer&#x20;

### v1.&#x20;

A rather straight forward solution is a two-pass algorithm using counting sort.\
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

```python
class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        
        Count0 = Count1 = 0
        for i in nums:
            if i == 0:
                Count0 += 1
            elif i == 1:
                Count1 += 1
        
        Count1 += Count0
        for index in range(0,len(nums)):
            if index < Count0:
                nums[index] = 0
            elif index < Count1:
                nums[index] = 1
            else:
                nums[index] = 2
```

### v2.

Could you come up with a one-pass algorithm using only constant space?

{% tabs %}
{% tab title="for" %}

```python
class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        
        index0, index1, index2 = 0, 0, len(nums)-1
        
        while index1 <= index2:
            if nums[index1] == 0:
                nums[index0], nums[index1] = 0, nums[index0]
                index1 += 1
                index0 += 1
            elif nums[index1] == 2:
                nums[index2], nums[index1] = 2, nums[index2]
                #index1 += 1
                index2 -= 1
            else:
                index1 += 1
            
            #print(index0,index1,index2)
            #print(nums)
```

{% endtab %}

{% tab title="while" %}

```python
class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        index0, index1 = 0, 0
        
        for i in range(0, len(nums)):
            v = nums[i]
            nums[i] = 2
            
            if v == 0:
                nums[index1] = 1
                index1 += 1
                nums[index0] = 0
                index0 += 1
            elif v == 1:
                nums[index1] = 1
                index1 += 1
```

{% endtab %}
{% endtabs %}