# My C++ solution with one pass and O(n) time and O(n) space

• ``````class Solution {
public:
//use counting sort
void sortColors(int A[], int n) {
int red = -1, white = -1, blue = -1;

for(int i = 0; i < n; i++){
if(A[i] == 0){
A[++blue] = 2;
A[++white] = 1;
A[++red] = 0;
}
else if(A[i] == 1){
A[++blue] = 2;
A[++white] = 1;
}
else if(A[i] == 2)
A[++blue] = 2;
}
}
};
``````

the clever thing is that use three variable to store the three colors' index position.
When you face A[i] == 0, all the variables add 1 because 0 is former.
Do the same thing to other 2 situation.

Ex:
If you just face 2, just need to assign 2 to the A[++blue], and "++blue" will increase "blue" with 1.
Next if you face 0, you will increase 3 variable and assign the number to A!

It will make sure you always get the right sorted array when you run the for loop.

• Your answer is brilliant. We have the same idea, but mine is less verbose and more generic.

``````class Solution {
public:
void sortColors(int A[], int n) {
int f[3]={0}; // store the frequencies
int i,j,k;
for(i=0;i<n;i++){
int cur=A[i];
f[cur]++;
int prev=cur;
// basically this loop will insert the new element, cur.
// same principle as the answer above, but condensed into a loop.
for(k=j=0;j<=2;j++){
k+=f[j]; // k is cumulative freq.
if(j>=cur&&f[j]){
// replace the element that is occupying the new element (cur)'s
//rightful place, and store the old element in prev
swap(A[k-1],prev);
}
}
}
}
};``````

• This post is deleted!

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

• there are 4 memory accesses (worst case) for each iteration. Maybe worse than a simple two passes solution.

• you can do ++blue, ++white, ++red without modifying A[] I think. And the space is O(1)?

• Could you change your title to O(1) space? Now it is O(n) and misleading.

• your solution is O(1) space, not O(n)

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