LeetCode June Challenge - Day 11

Problem: LeetCode June Challenge - Day 11

Ideas:

  1. I won’t do the trivial solution that the problem mentions. Let’s try to do it in one pass.
  2. My solution consists in 3 pointers, the current element, the last zero at the beginning and the first 2 at the end. I will do one pass, swapping zeros to the beginning and twos to the end.

Solution:

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

        for(int i=0; i<i2;){
            if(nums[i] == 0)
                swap(nums[i], nums[++i0]);
            if(nums[i] == 2)
                swap(nums[i], nums[--i2]);
            if(nums[i] == 1 || i0 >= i)
                ++i;
        }
    }
};