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!