class Solution {
public:

    // Memory Complexity O(1)
    // Run-time Complexity O(n2)
    /*int removeDuplicates(vector<int>& nums) {

        if (nums.empty()) {
            return nums.size();
        }

        int i = 0;
        while (i < nums.size() - 1) {

            if (nums[i] == nums[i + 1])
                nums.erase(nums.begin() + i); //O(n)
            else
                ++i;
        }

        return nums.size();
    }*/

    // i = 0; it = 0; j = 1
    // 0 1 1 1 2 2 3
    // i = 1; it = 1; j = 2
    // 0 1 1 1 2 2 3
    // i = 4; it = 2; j = 5
    // 0 1 2 1 2 2 3
    // i = 5; it = 3; j = 6
    // 0 1 2 3 2 2 3
    // Memory Complexity O(n2)
    // Run-time Complexity O(1)
    int removeDuplicates(vector<int>& nums) {

        int it = 0;
        int i = 0;
        while(i<nums.size())
        {
            int j = i + 1;
            while(nums[i] == nums[j])
                ++j;

            nums[it++] = nums[i];
            i = j;
        }

        return it;
    }
};