2-line simple Python solution, is this a cheating solution?


  • 0
    B
    class Solution(object):
        def removeElement(self, nums, val):
            """
            :type nums: List[int]
            :type val: int
            :rtype: int
            """
            while val in nums:
                nums.remove(val)
            return len(nums)
    

  • 0

    I'd say not cheating, just very bad.


  • 0
    B
    This post is deleted!

  • 0
    B

    @StefanPochmann
    Thank you for your reply.
    I'm a beginner learning programming so I'm a little confused. Could you please tell me why it's very bad? I checked "Accepted Solutions Runtime Distribution" and it says that the runtime beats 88.80 % of python submissions. So what's good and what's bad for an algorithm?


  • 0

    Well it's only O(n2). And O(n) is easy. It just seems fast because the judge is very weak here, only has tiny test cases. Maybe because this is from the earliest days of LeetCode.


  • 0
    B

    @StefanPochmann
    Got it. Thank you for you explaination. The return statement is left out because of my misunderstanding. These codes can be accepted without return statement, and the description says " you must do this in place ", so I think it's enough to change the nums without return anything. My fault.


  • 1

    @bluesweater If it's accepted without return statement, that's a bug in the judge. It shouldn't get accepted. Probably the judge does something like checking nums[:output], which without return statement turns into nums[:None], which is a copy of the whole nums. Combined with your actual shrinking of the list, that then appears to be correct.

    Anyway, here's a little test, testing your solution and the normal O(n) solution on a certain input with 10,000 elements (which isn't very big, I think some more recent problems have inputs with 100,000 elements or so):

    from time import time
    
    class Solution(object):
        def removeElement(self, nums, val):
    
            nums = [0] * 5000 + [1] * 5000
            val = 1
            t0 = time()
            while val in nums:
                nums.remove(val)
            print time() - t0
    
            nums = [0] * 5000 + [1] * 5000
            t0 = time()
            i = 0
            for num in nums:
                if num != val:
                    nums[i] = num
                    i += 1
            print time() - t0
    

    Doing "Run Code" with that prints times like these:

    0.671131134033
    0.000586986541748
    

    So already for this medium size input, your code is over 1000 times slower than the normal solution.


  • 0
    B

    @StefanPochmann
    I've learned a lot. Thank you so much~


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.