Sort Colors

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,

• while i < end and nums[i] == 2, we should be swapping the value present at nums[i] with nums[end] and decrementing end
• then, consequently, if nums[i] == 0, we should be swapping the value present at nums[i] with nums[start] and incrementing start

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: O(n) where n denotes the size of nums
• Space: O(1)

time taken

• 4 minutes and 31 seconds