Sort Colors

MEDIUM

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.

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

Example 3:

```Input: nums = [0]
Output: [0]
```

Example 4:

```Input: nums = [1]
Output: [1]
```

Constraints:

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

• Could you solve this problem without using the library’s sort function?
• Could you come up with a one-pass algorithm using only `O(1)` constant space?

The Dutch national flag problem is a computer science programming problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (it does not matter how many balls there are), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

Following is an one pass constant space implementation:

```class Solution {
public void sortColors(int[] nums) {

int l = 0;
int r = nums.length - 1;
int cur = 0;
while(cur <= r){
int current = nums[cur];
if(current == 2){
swap(nums, cur, r);
r--;
}else if(current == 0){
swap(nums, l++, cur++);
}else{
cur++;
}
}
}

private void swap(int[] nums, int l, int r){
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}
}
```

Categories: Array