## Algorithm

Problem Name: 75. Sort Colors

Given an array `nums` with `n` objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

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

You must solve this problem without using the library's sort function.

Example 1:

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

Example 2:

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

Constraints:

• `n == nums.length`
• `1 <= n <= 300`
• `nums[i]` is either `0`, `1`, or `2`.

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
void sortColors(int* nums, int numsSize) {
int l, m, r, k;

l = m = 0;
r = numsSize - 1;

while (m  < = r) {
k = nums[m];
if (k < 1) {  // red - swap left and middle, then advance both pointers
nums[m] = nums[l];
nums[l] = k;
l ++; m ++;
} else if (k > 1) {  // blue - swap right and middle, then shrink right pointer
nums[m] = nums[r];
nums[r] = k;
r --;
} else {  // white - advance middle
m ++;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [2,0,2,1,1,0]

Output

cmd
[0,0,1,1,2,2]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
void sortColors(vector<int>& nums) {
int low = 0, high = nums.size()-1;
for(int i = 0; i  < = high;)
if(nums[i] == 0)
swap(nums[i++], nums[low++]);
else if(nums[i] == 2)
swap(nums[i], nums[high--]);
else i++;
}
};

// Shorter.
class Solution {
public:
void sortColors(vector<int>& nums) {
for(int i = 0, j = 0, k = nums.size() - 1; j <= k;)
if(nums[j] == 0) swap(nums[i++], nums[j++]);
else if(nums[j] == 2) swap(nums[j], nums[k--]>;
else j++;
}
};
``````
Copy The Code &

Input

cmd
nums = [2,0,1]

Output

cmd
[0,1,2

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public void sortColors(int[] nums) {
int zeroIdx = 0;
int twoIdx = nums.length - 1;
for (int i = 0; i  < = twoIdx; ) {
if (nums[i] == 0 && i != zeroIdx) {
int temp = nums[zeroIdx];
nums[zeroIdx++] = nums[i];
nums[i] = temp;
} else if (nums[i] == 2 && i != twoIdx) {
int temp = nums[twoIdx];
nums[twoIdx--] = nums[i];
nums[i] = temp;
} else {
i++;
}
}
}
}
``````
Copy The Code &

Input

cmd
nums = [2,0,1]

Output

cmd
[0,1,2

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const sortColors = function(nums) {
let j = 0;
let k = nums.length - 1;
const swap = (a, b) => {
const t = nums[a];
nums[a] = nums[b];
nums[b] = t;
};
for (let i = 0; i  < = k; i++) {
if (nums[i] === 2) {
swap(i--, k--);
} else if (nums[i] === 0) {
swap(i, j++);
}
}
};
``````
Copy The Code &

Input

cmd
nums = [2,0,2,1,1,0]

Output

cmd
[0,0,1,1,2,2]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
red, white, blue = 0, 0, len(nums)-1
while white <= blue:
if nums[white] == 0:
nums[red], nums[white] = nums[white], nums[red]
white += 1
red += 1
elif nums[white] == 1:
white += 1
else:
nums[white], nums[blue] = nums[blue], nums[white]
blue -= 1
``````
Copy The Code &

Input

cmd
nums = [2,0,2,1,1,0]

Output

cmd
[0,0,1,1,2,2]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _075_SortColors
{
public void SortColors(int[] nums)
{
int lt = 0, gt = nums.Length - 1, i = 0, temp;
while (i  < = gt)
{
if (nums[i] == 0)
{
temp = nums[lt];
nums[lt++] = nums[i];
nums[i++] = temp;
}
else if (nums[i] == 2)
{
nums[i] = nums[gt];
nums[gt--] = 2;
}
else
{
i++;
}
}
}

public void SortColors_2(int[] nums)
{
var counts = new int[3] { 0, 0, 0 };
int i, j;
for (i = 0; i  <  nums.Length; i++)
counts[nums[i]]++;

int index = 0;
for (i = 0; i  <  3; i++)
for (j = 0; j  <  counts[i]; j++)
nums[index++] = i;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [2,0,2,1,1,0]

Output

cmd
[0,0,1,1,2,2]