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.
Latest comments (2)
Very informative, thank you. Have you tried to using to reduce?
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.