75. Sort Colors
1. Description
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.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
2. Follow Up
- 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?
3. Example
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]
4. Constraints
- n == nums.length
- 1 <= n <= 300
- nums[i] is 0, 1, or 2.
5. Solutions
My Accepted Solution
n = m_nums.size()
Time complexity: O(n)
Space complexity: O(1)
// meet conditions of two Follow Up
class Solution
{
public:
// void sortColors(vector<int>& nums)
void sortColors(vector<int> &m_nums)
{
for(int left = 0, fastLeft = 0, right = m_nums.size()-1; fastLeft < right; )
{
// we hope we could put all 0 at the beginning of the array and all 2 at the end of the array
// if all of them could stay at their corect place, all 1 must stay at their right positions as well
// so we go through the array, if any 0 and 2 doesn't stay at its correct position, we exchange them, which could help at least one more item get its correct position
while(left < right && m_nums[left] == 0) ++left; // pass all 0
while(left < right && m_nums[right] == 2) --right; // pass all 2
fastLeft = max(left, fastLeft); // this code works only when the fastLeft is zero, otherwise it must be bigger than left
if(left < right) // we have to be careful of stack overflow
{
if(m_nums[left] & m_nums[right] == 1) // the values of both left index and right index are 1, we can't continue our exchange progress through swap these two pointers
{
while(fastLeft < right && m_nums[fastLeft] == 1) fastLeft++; // we pass all 1 quickly
// since out conditon to end the circulation is fastLeft < right, so we only go through the array for one time
if(fastLeft < right)
{
swap(m_nums[left], m_nums[fastLeft]);
// we get a value which is not 1, so we could continue our exchange progress
}
}
else // continue our exchange progress
{
swap(m_nums[left], m_nums[right]);
}
}
}
}
};
5.1 Dutch National Flag Problem
n = m_nums.size()
Time complexity: O(n)
Space complexity: O(1)
// meet conditions of two Follow Up
class Solution
{
public:
// void sortColors(vector<int>& nums)
void sortColors(vector<int>& m_nums)
{
int red = 0, white = 0, blue = m_nums.size() - 1;
while(white <= blue)
{
if(m_nums[white] == 0)
{
swap(m_nums[red], m_nums[white]);
red += 1;
white += 1;
}
else if(m_nums[white] == 1)
{
white += 1;
}
else
{
swap(m_nums[white], m_nums[blue]);
blue -= 1;
}
}
}
};
5.2 Magic
n = m_nums.size()
Time complexity: O(n)
Space complexity: O(1)
// meet conditions of two Follow Up
// it works like hash table
// it working status like brush, we brush all colors to blue, and the white color trys its best to brush colors to white, as same as red
class Solution
{
public:
void sortColors(vector<int>& m_nums)
{
int red = 0, white = 0, blue = 0;
for(auto color : m_nums)
{
if(color == 0)
{
m_nums[blue++] = 2;
m_nums[white++] = 1;
m_nums[red++] = 0;
}
else if(color == 1)
{
m_nums[blue++] = 2;
m_nums[white++] = 1;
}
else
{
blue++;
}
}
}
};