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!