Remove Duplicates from Sorted Array - Leetcode

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.

Comments

[Mohamed Saleh]

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.

[Mamadou Korka Diallo]

Very informative, thank you. Have you tried to using to reduce?