Given a sorted array of numbers with duplicates, remove all duplicates from array, leaving one of each number. Return the length of the array.
For example:
input = [1,1,2,2,2,3,3]
output = [1,2,3]
This problem is relatively straightforward. If you want to accomplish it using O(n) time and 0(1) space, you want to use the two pointer method. I will instantiate two pointers, i and j, set to 0 and 1, respectively. I will use a while loop, and I will check whether the num with i index is equal to num with j index. If not, I increment both of them by 1. If they are equal, I pop out the number with j index.
def removeDuplicates(nums):
i, j = 0, 1
while j < len(nums):
if nums[i] != nums[j]:
i += 1
j += 1
elif nums[i] == nums[j]:
nums.pop(j)
return len(nums)
In javascript, it's similar:
function removeDuplicates(nums):
let i = 0;
let j = 1;
while (j< nums.length) {
if (nums[i] != nums[j]) {
i+= 1;
j+= 1;
} else if (nums[i] == nums[j]) {
nums.splice(j, 1);
}
return nums.length;
}
In javascript function, I use splice instead of pop since javascript doesn't pop by index. Splice takes the element with the specified index, and if there's a 1 as parameter, it removes that element.
Top comments (2)
Nice write-up. Good idea to use 2 pointers to improve the time complexity while using constant space.
However, in the code the pop(j) has a worst time complexity of O(n) since all the elements after that index have to shift to the left (making the collective worst time complexity O(n^2)).
One trick get around this is to swap j and the last element of the list and then do a pop() which should reduce the time of the pop to be O(1) since it's removing the last element of the list.
Very informative, thank you. Have you tried to using to reduce?