## Question

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]
```

## Algorithm

- You cannot assume the amount of 0, 1, 2 are the same.
- Basically the idea is to put the 0s at the left side and 2s at the right side, and the positions left in the middle are 1s
- There should be a optimization that we can solve it without extra space, that is to do it in-place.
- I was stuck at where to stop the iteration and swap-> it's index2.

## Code

class Solution { public void sortColors(int[] nums) { int[] res = new int[nums.length]; for (int i = 0; i < nums.length; i++) { res[i] = nums[i]; nums[i] = 1; } int index0 = 0, index2 = nums.length - 1; for (int i = 0; i < nums.length; i++) { if (res[i] == 0) { nums[index0++] = 0; } else if (res[i] == 2) { nums[index2--] = 2; } } } }

class Solution { public void sortColors(int[] nums) { int index0 = 0, index2 = nums.length - 1; int index = 0; while (index <= index2) { if (nums[index] == 0) { swap(nums, index0--, index++); } else if (nums[index] == 2) { swap(nums, index2--, index++); } else { index++; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }