Remove Duplicates from Sorted Array in O(1) Space

Question

Question: https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/

Basically, duplicates in a sorted array needs to be removed without creating a new one. I have tested my solution, and it falters when there are 3, 5, 7 (and so on) number of duplicates of the same number. What techniques can I try?

Code:

def removeDuplicates(nums):
    i = 0 # moving pointer
    end = len(nums)-1 # points to the end of the array
    # iterates over the array
    while i != end:
        # if current number is equal to the next
        if (nums[i] == nums[i+1]):
            # pop it off
            nums.pop(i)
            # decrement the length of array
            end -= 1
        i += 1 # increments the moving pointer
    return i + 1


nums = [0,0,1,1,1,2,2,3,3,4]
print(removeDuplicates(nums))

Changing the length of a list while iterating over it is tricky. In this case it should work if you add an `else:` to the `if` and do the `i += 1` only in the `else` part. BTW, `if` is not a function, so you can and should remove the parentheses. `if (nums[i] == nums[i+1]):` should be `if nums[i] == nums[i+1]:`. — Matthias, Oct 15 '22 at 16:36
Stack Overflow is not the right site for "Discussion regarding...". Your title mentions O(1), which is of course not possible, as you need to scan all values in the input, which already needs O(n). But your algorithm idea is O(n²), because of using `.pop(index)`. Try rethinking this, and not using `.pop`. Note that the length of the list does not have to change -- read carefully the challenge description to grasp that important aspect. — trincot, Oct 15 '22 at 16:38
I would use two indices (i, j) where i is trailing and j finds the next elements you want to put at num[i]. — Allan Wind, Oct 15 '22 at 16:38
@Sören You're right, the task says: "Do not allocate extra space for another array.". But I wonder if one could use an additional `set`. — Matthias, Oct 15 '22 at 16:43
Reopening, none of the referenced answers for Python actually achieve O(1) space and O(n) time. — Matt Timmermans, Oct 15 '22 at 23:08
@MattTimmermans where do you get the O(n) time requirement from? Also, the question is about why only every second element was removed, which is answered in the dupe. — Sören, Oct 16 '22 at 06:15
@trincot But ... but ... it wasn't me who asked the question. — Matthias, Oct 16 '22 at 08:52
This question has been answered before with a solution that uses O(1) space and 0(n) time: [Remove Duplicates from Sorted Array - Why is my python code wrong?](https://stackoverflow.com/questions/70553719/remove-duplicates-from-sorted-array-why-is-my-python-code-wrong) — trincot, Oct 16 '22 at 09:09
@Sören I doubt there is a practical reason to require O(1) space that doesn't also require O(n) time. — Matt Timmermans, Oct 16 '22 at 12:08

Matt Timmermans · Accepted Answer · 2022-10-16T12:14:47.477

The way to remove duplicates from a sorted list in O(1) space and O(n) time is to pack the unique elements at the beginning of the list, and then truncate the list:

def removeDuplicates(nums):
    #new length
    newlen = 0
    for val in nums:
        if newlen == 0 or nums[newlen-1] != val:
            # no matter what, we've already retrieved nums[newlen],
            # so this write doesn't interfere with the rest of the loop
            nums[newlen] = val
            newlen += 1
    
    # delete the unused space at the end of the list, all at once
    if newlen < len(nums):
        del nums[newlen:]
    return newlen


nums = [0,0,1,1,1,2,2,3,3,4]
print(removeDuplicates(nums))
print(nums)

Your original code fails, because you remove elements from the start of the array as you're iterating through the end. The iteration remembers its position in the array in i, and when you remove an element, the elements after it are shifted into lower positions.

You could fix that by putting the i += 1 into an else, but the resulting implementation would still take O(N^2) time, which isn't really acceptable.

Thank you. It solves the question, but my original query remains. Why does my solution doesn't works when there are 3, 5, 7... duplicates of the same number? Can you please shed some light on that. — Rhodey, Oct 16 '22 at 04:24

Remove Duplicates from Sorted Array in O(1) Space

1 Answers1