1

This is a question from Leetcode. Given this sorted array nums = [0,0,1,1,1,2,2,3,3,4]

I want the output to be nums = [0,1,2,3,4]

However my code...

    low = nums[0] - 1
    
    for num in nums:
        if num == low:
            nums.remove(num)
        else:
            low = num
    
    print(nums)

...produced this output: [0,1,1,2,2,3,4]

Can anyone please shed some light on where the error is?

smci
  • 32,567
  • 20
  • 113
  • 146
superStar
  • 23
  • 4
  • In Python we say 'list' not 'array' as C/C++/Java would. – smci Jan 02 '22 at 05:53
  • Related: [How to remove items from a list while iterating?](https://stackoverflow.com/questions/1207406/how-to-remove-items-from-a-list-while-iterating). There are at least 100+ duplicates or near-duplicates of this question. – smci Jan 02 '22 at 05:56

3 Answers3

2

You're removing from the array while iterating over it. That can cause problems, as the memory in the list is shifting as you're accessing it.

Here's a one-liner:

# set() removes duplicates.
# We need to call sorted() on the set, as sets don't preserve insertion order (thanks Kelly Bundy!)
return sorted(set(nums))

Edit: Apparently, LeetCode asks for solutions that use O(1) memory. Here’s an alternate solution that meets the constraints of the original problem.

They also ask for a bunch of other weird quirks in the solution, so if you think something's off, read the problem statement before commenting or voting.

This solution works by keeping track of an index to insert new elements and the last element we've seen -- if we see a new element, we add it at the insertion index and increment our insertion index by one.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        insertion_index = 1
        previous_number = nums[0]
        for i in range(1, len(nums)):
            if nums[i] != previous_number:
                nums[insertion_index] = previous_number = nums[i]
                insertion_index += 1
        return insertion_index
BrokenBenchmark
  • 18,126
  • 7
  • 21
  • 33
  • Thank you very much for your help! I forgot to mention that one of the requirements is "Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory." Will using set(nums) require extra space? – superStar Jan 02 '22 at 05:13
0

The issue lies in the fact you are removing elements from the array you are looping through.

After the 0 at index 1 is removed (during the second iteration of the loop), the next value of num will be the second 1, at index 2 of the nums list (after removing the 0), which is at index 3 initially.

Instead the easiest thing to do is to loop through the indices of the list in reverse, and use this method to get the current num and use the same content of the loop you already use.

Edit: Typo

Niklas Burggraaff
  • 61
  • 3
  • 1
    This works, but worst case would take quadratic time (e.g. remove nothing in the back half of the array, then remove all but one element in the front half). – BrokenBenchmark Jan 02 '22 at 06:03
  • @BrokenBenchmark I think it would actually be worse the other way around: If the back half needs removal and the front half doesn't. – Kelly Bundy Jan 02 '22 at 06:12
  • In that case, you’d just be removing from the end of a list O(n) times, which is O(n). Contrast that with removing from the front half, where you’d have to shift O(n) elements over with each deletion. Perhaps the use of “front” and “back” half was a bit ambiguous here. – BrokenBenchmark Jan 02 '22 at 06:14
  • @BrokenBenchmark But they said *"use the same content of the loop you already use"*. Which uses `nums.remove(num)`. [Here](https://tio.run/##bZDRaoQwEEXf8xXzshhbLRvsQxH8EpGi69gNTSY2xpZ@vU2M667QgQQyk3Nn7oy/7mqoeBvtsgzWaHBSo3Qg9Wis216M9TjATPKL06yntGTgQ5kfqCAk6lw08AxiTa/XYCxIkAS2pQ/kCimSkIPIIF/PJhPC125SstmzcoiFKrS6f96A6cWiNt8YhNO9iGrC49d9zOgiOHp04XwxuuSq1V3flg9Gs8B1aCsRO1h0syVITq89aKmUnPBiqJ8SOAF38AQCi5Qx8pri7IOFPbzf91BsTUcryfEkGgC/d3JwbdVQJlkcsD43Xo38Un0PxyNNqY9/@K69fEYcbvyR8jI1rYIHPmXL8gc) is how I think they meant the code, and a demonstration that my case takes over 50 times longer. – Kelly Bundy Jan 02 '22 at 06:25
  • @KellyBundy I've thought about this a bit, and it still isn't clear to me why there's a 50x runtime difference. In both cases, a call to `.remove()` would need to perform some operation on every element in a list (removing, comparing, or shifting). Am I missing something? – BrokenBenchmark Jan 08 '22 at 04:11
  • 1
    @BrokenBenchmark I guess you're missing that object comparisons are **far** slower than shifting references (the latter is much less work and even is cache-friendly). And my case causes far more comparisons than yours. – Kelly Bundy Jan 08 '22 at 18:04
  • [**80**x runtime difference](https://tio.run/##bVHbasMwDH33V@ilxF6TdVkolEK@pISRNvJq6kvmOBv7@sy33mCCOEhH51hHHn/d2ehmN9pl4dYocEKhcCDUaKzLGYmI7fXgfxmZzjPnEgkZkMOsxRfVs5rYnoAPaX6ghVA4VHUHa6hjOR7cWBAgdND7RCpRJyZUUJdQxS/LhPDYVUp0t6rgCWjDVffmTJheLSrzjUGY3UCUEz633sZMLoLZRxfOg2kBVPbqOPT7B6Nl4B3RtnW6waKbrYZitR1ACSnFhCejh6mAFVAHL1BjwwjRXnP75oNEW7DZwDtJ0/r8oDrfqcgFcfSpF3E0rUkxRvLKaUAZCXv8uO@xyUOPVmhHiyzpH047OPeS74syGczIGqIM@4d07E@XxIErKQ60htTwRGJkWf4A) if I shuffle the numbers to keep, as that makes my case more cache-unfriendly (yours isn't affected). – Kelly Bundy Jan 08 '22 at 18:26
  • Makes sense. Thanks for the explanation! – BrokenBenchmark Jan 08 '22 at 18:37
-1

You can use set as follows:

new_list = list(set(nums))
Sree Teja
  • 27
  • 6
  • As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Jan 02 '22 at 07:35