This is the warm-up sort of problem to one we’ve seen earlier. The solution is the same spirit.

This is a nice example (finally!) of my drumbeat that a lot of these problems are really reflections of the same “root” problem. While there are still many such root problems, after a while you start to see repetitions, in addition to the shared fundamental material of course.

So we have the same sort of solutions. The first is the C++ algorithm, which is likely “too close to the real problem”. The interviewer would naturally ask “please implement the “unique” function you use there.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        auto new_end = std::unique(std::begin(nums), std::end(nums));
        return std::distance(std::begin(nums), new_end);
    }
};

So let’s do that in Python. There is probably a similar-enough algorithm, but ironically let’s just do a much more explicit version.

class Solution(object):
    def removeDuplicates(self, nums):
        i = 0
        j = 0
        while i < len(nums):
            nums[j] = nums[i]
            j += 1
            new_i = i + 1
            while new_i < len(nums) and nums[i] == nums[new_i]:
                new_i += 1
            i = new_i
        return j

I actually really like this question. There are multiple ways of solving it. The loops involved here are understandable, but different from the “cliche” for-loops. They also start the idea of having 2 different indices into the same array, a powerful tool that a lot of novice programmers seem pretty surprised by.