Simple python leetCode not accepted on technicality?

Question

I have a very simple algorithm question here, which asks to remove duplicates from a list and return the length of the new list.

Here's my code in py3:

class Solution:
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = list(set(nums))
        return len(nums)

This works fine when I test it in my terminal. But according to leetCode, input: [1,1,2] puts out [1,1] instead of [1,2]. Assuming leetCode doesn't have a bug, I can only come to the conclusion that there's something going on with the scope of nums? Maybe nums is being treated like a local variable when set using nums = list(set(nums))?

The question on the site you linked to explicitly says: "Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory." (emphasis mine). That's not what you're doing - you're allocating a set, leaving the initial list exactly as it was, and creating a new list based off of the set, and returning that. You're using O(n) of memory, not O(1). — Scott Mermelstein
– Scott Mermelstein, Commented Mar 2, 2018 at 15:15
I might be missing something, but the nums value given is a tuple which is immutable. How are you supposed to change it in place without creating a new sequence object? — dfundako
– dfundako, Commented Mar 2, 2018 at 15:28
@dfundako, I really doubt the input is immutable, since they tell you that you are given an array (that's a list in python) — jtagle
– jtagle, Commented Mar 2, 2018 at 15:32
@thestateofmay, it's not wierd, that's how it is supposed to work with python — jtagle
– jtagle, Commented Mar 2, 2018 at 15:47

jtagle · Accepted Answer · 2018-03-02 16:02:55Z

1

I can't test code now on the web you linked. But I think you can imagine the testcase as follow (I'm just guessing here, so this answer might not work properly):

class Solution:
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = list(set(nums))
        return len(nums)

nums = [1, 1, 2]
solver = Solution()
length = solver.removeDuplicates(nums)
print(nums[:length])

So, by watching the test case, you can see that you actually get [1, 1], since you are not modifying the list, but you are creating a new local variable within the method scope. You could try doing something like this maybe:

class Solution:
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        while i < len(nums) - 1:
            if nums[i] == nums[i+1]:
                del nums[i]
            else:
                i += 1
        return len(nums)

nums = [1, 1, 2, 2, 2, 3]
solver = Solution()

length = solver.removeDuplicates(nums)
print(nums[:length])

When they ask for an algorithm "in-place" you are not supposed to create new variables (or overwritte the old one with a new list), that's not O(1) extra memory, it's O(n), since you are creating a new copy.

EDIT A bit more explanation

What is happening with your code, is that you create a new local variable in a new memory space (In case you know about computers, you create it in the stack) therefore, inside your function you lose the reference to the pointer that gives you the outter nums variable (the original list). So the nums variable in the function (stack) is setted as a list created by iterating all different elements of the original list. Then, you really get a copy that meet all the requirements and is stored in the stack, but the old list stays the same. Then, when you exit your function, the stack variable is lost, so when you access to the num variable, you will get the old one (the original).

To understand what's going on here, you can read this to learn about scopes, and this to learn about passing arguments to functions.

edited Mar 2, 2018 at 16:02

answered Mar 2, 2018 at 15:26

jtagle

3121 silver badge8 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

bli00 Over a year ago

hmm it seems if I create a new variable and set nums equal to it nums doesn't change at all. Which seems kind of weird since manipulating individual elements within nums like the way you described it changes nums

jtagle Over a year ago

Give me a sec, I'll try to explain better on the answer to see. ¿Have you coded in C or more low level languages?

bli00 Over a year ago

so even though nums is the same name as the argument, nums = list(set(nums)) is actually creating a new local variable? then how can one write a void function that modifies the given inputs?

jtagle Over a year ago

Indeed, you are creating a new variable. Being a void function doesn't mean you can't change variables inside them. You can create a void function that recieves an array, modify it and then the function doesn't return.

Collectives™ on Stack Overflow

Simple python leetCode not accepted on technicality?

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related