LeetCode Challenge Description

Solution

We need to modify the input array, and use only $O(1)$ extra memory. With a variable cnt to track the current count of result array, nums[cnt - 1] is the previous value of result array, compare it with current iterated element to determine whether add it to the result array.

Time complexity: $O(N)$.

CPP version:

class Solution {
public:
  int removeDuplicates(vector<int>& nums) {
    if(nums.size() == 0) return 0;
    size_t cnt = 1;
    for(size_t i = 1; i < nums.size(); i++) {
      if(nums[i] != nums[cnt-1])
        nums[cnt++] = nums[i];
    }
    return cnt;
  }
};

Python Solution

class Solution:
    def removeDuplicates(self, nums):
        cnt = 1
        if len(nums)==0:
            return 0
        for i in range(1,len(nums)):
            if nums[i] != nums[i-1]:
                nums[cnt] = nums[i]
                cnt +=1
        return cnt

A variant challenge: Remove Duplicates from Sorted Array II

Remove Duplicates from Sorted Array II is a similar challenge, but the elements in result array can only appeared at most twice.

For this trivial different, we compare nums[i] and nums[cnt-2] during the loop:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() <= 2) return nums.size();
        int cnt = 2;
        for(int i=2; i < nums.size(); i++) { 
            if(nums[i] != nums[cnt-2]) 
                nums[cnt++] = nums[i];
        }
        return cnt;
    }
};

Preparing for an interview? Check out this!