Coder's Cat

LeetCode: Remove Duplicates from Sorted Array

2020-01-30

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!