DEV Community

Shirley
Shirley

Posted on

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]
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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)

Collapse
 
salehmdev profile image
Mohamed Saleh • Edited

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.

Collapse
 
herico profile image
Mamadou Korka Diallo

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