# Sharing C++ solution with Good Explanation

• The solution requires the use of tracking 3 positions, the Low, Mid and High.

We assume that the mid is the "Unknown" area that we must evaluate.

If we encounter a 0, we know that it will be on the low end of the array, and if we encounter a 2, we know it will be on the high end of the array.

To achieve this in one pass without preprocessing (counting), we simply traverse the unknown will generating the low and high ends.

Take this example:

Assume our input is: 1 0 2 2 1 0 (short for simplicity).

Running the algorithm by hand would look something like:

``````    1 0 2 2 1 0
^         ^
L         H
M

Mid != 0 || 2
Mid++

1 0 2 2 1 0
^ ^       ^
L M       H

Mid == 0
Swap Low and Mid
Mid++
Low++

0 1 2 2 1 0
^ ^     ^
L M     H

Mid == 2
Swap High and Mid
High--

0 1 0 2 1 2
^ ^   ^
L M   H

Mid == 0
Swap Low and Mid
Mid++
Low++

0 0 1 2 1 2
^ ^ ^
L M H

Mid == 2
Swap High and Mid
High--

0 0 1 1 2 2
^ ^
L M
H

Mid <= High is our exit case
``````

Implemented in C++, it looks like:

``````class Solution {
public:
void sortColors(vector<int>& nums)
{
int tmp = 0, low = 0, mid = 0, high = nums.size() - 1;

while(mid <= high)
{
if(nums[mid] == 0)
{
tmp = nums[low];
nums[low] = nums[mid];
nums[mid] = tmp;
low++;
mid++;
}
else if(nums[mid] == 1)
{
mid++;
}
else if(nums[mid] == 2)
{
tmp = nums[high];
nums[high] = nums[mid];
nums[mid] = tmp;
high--;
}
}
}
};``````

• Nice explanation, thanks

• So far the best explanation for this problem I've seen. Thanks !

• @Atomsktron Thank you so much for offering the explanation and the solution

• This post is deleted!

• Nice thought! Just a heads-up. C++ has built-in swap, and there is no need to have int temp;

``````void sortColors(vector<int>& nums) {
int l{}, mid{}, h{nums.size() - 1};
while (mid <= h)
if (nums[mid] == 0)
swap(nums[mid++], nums[l++]);
else if (nums[mid] == 1)
mid++;
else
swap(nums[mid], nums[h--]);
}``````

• Another note, the swap is not even necessary either because we know what the value of nums[mid] is entering every if condition.

So,

``````if(nums[mid] == 0)
{
tmp = nums[low];
nums[low] = nums[mid];
nums[mid] = tmp;
low++;
mid++;
}
``````

becomes

``````if(nums[mid] == 0) {
nums[mid] = nums[low];
nums[low] = 0;
low++;
mid++;
}
``````

• ``````Why when mid==2 satisfy, we dont need mid++?
``````

@Atomsktron
See the follow. Thks.
Mid == 2
Swap High and Mid
High--

• @Atomsktron Lovely.

• @xhp0407 The reason why we don't need mid++ is because on the right side of mid, it could be a 0 swapped back, that will need be further swapped to left to mid. This is a problem when doing scanning from left to right. If doing scanning from right to left, we have following

``````    public void sortColors(int[] nums) {
if (nums == null || nums.length == 0)
return;
int n = nums.length;
int i = n - 1, j = 0, k = n - 1;
while (j <= i) {
if (nums[i] == 0) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
j++;
} else if (nums[i] == 1) {
i--;
} else {
int t = nums[i];
nums[i] = nums[k];
nums[k] = t;
k--;
i--;
}
}
}
``````

• @daniexia This explanation is great and necessary, thanks

• @Atomsktron Thanks for the nice solution.

My method is straightforward.
What I've done is simply cut the nums into three part (red, white, blue) and combine them.

``````class Solution {
public:
void sortColors(vector<int>& nums) {
vector<int> red, white, blue;
vector<int> res;
for(int i = 0; i < nums.size(); ++i)
{
if(nums[i] == 0)
{
red.push_back(nums[i]);
continue;
}
if(nums[i] == 1)
{
white.push_back(nums[i]);
continue;
}
if(nums[i] == 2)
{
blue.push_back(nums[i]);
continue;
}
}
res.insert(res.end(), red.begin(), red.end());
res.insert(res.end(), white.begin(), white.end());
res.insert(res.end(), blue.begin(), blue.end());
nums = res;
}
};

``````

• Good explanation. Actually, someone who familiar with partition in Quicksort will find that the idea is the same.

• Thanks, very clear explanation. Easy to understand.
Here is the Python version:

``````  def __swap(self, l, i, j):
tmp = l[i]
l[i] = l[j]
l[j] = tmp

def sortColors(self, nums):
low, mid, high = 0, 0, len(nums)-1
while mid <= high:
if nums[mid] == 0:
self.__swap(nums, mid, low)
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
elif nums[mid] == 2:
self.__swap(nums, mid, high)
high -= 1
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.