75. Sort Colors

TODO

Problem

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?

Solution

Two Pointer - O(n) time - O(1) space

1. Use a variable to track current color to sort
2. Start slow at i = 0
3. Start fast at i = 1
4. if slow is current color, move slow and fast
5. if not
   1. move fast to find the next current color
   2. swap the two elements
   3. if not found, increment current color and continue

class Solution {
public:
	void sortColors(vector<int>& nums) {
		int currentColor = 0;
		for (int slow = 0; slow < nums.size(); slow++) {
			
		}
	}
}