75: Sort-Colors
Medium

I swear I have solved this problem before…

Anyways, the intuition for this solution is, as long as we place the 0’s and 2’s in the correct position, the remaining 1’s will naturally end up in the correct position as well.

Then, since 0’s always end up at the start of nums and 2’s always end up at the end of nums, we can initialize two pointers to track where we should be placing 0s and 1s: start and end.

Now, all we need to do now is iterate between 0 and end inclusively (since all the values past end are all 2’s, there is no need to iterate through them). During each iteration i,

Then, our colours will be sorted in-place.

code

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int start = 0, end = nums.size()-1;

        for (int i = 0; i <= end; ++i) {
            while (i < end && nums[i] == 2) {
                swap(nums[i], nums[end]);
                --end;
            }

            if (nums[i] == 0) {
                if (i != start) {
                    swap(nums[i], nums[start]);
                }
                ++start;
            }
        }
    }
};

complexity

time taken