Possibly O(N) Python answer. Can somebody verify?


  • 0
    V
    class Solution(object):
        def moveZeroes(self, nums):
            i = 0
            zerolist = []
            nonzerolist = []
            while i < len(nums):
                if nums[i] == 0:
                    zerolist.append(0)
                else:
                    nonzerolist.append(nums[i])
                i = i + 1
            nums[:] = nonzerolist + zerolist

  • 0
    This post is deleted!

  • 0
    V

    Sorry my bad!! did not realize indentation got messed up ... please check now ...BTW I am assuming pop and append perform good ...


  • 0

    The "class..." is still outside the block and the block contains an indentation error...

    Anyway... append averages O(1), but pop(i) of course takes linear time. See https://wiki.python.org/moin/TimeComplexity.

    Your solution is only O(n^2).


  • 0

    And even if pop(i) were O(1), your solution would only be O(n^2), since you're restarting from the start after every single zero.


  • 0
    V

    Even if I restart I do not traverse the whole list since solution breaks when i reaches the last processed element "last" ... i hope this clarifies .


  • 0

    I know that. And it's irrelevant.


  • 0
    V

    Okay fixed the two loops ... this works for most cases ... though leetcode is going of out memory ... I can fix this by using pop instead of moving slide ...


  • 0

    Maybe there's a special memory limit to prevent people from using an extra list. Anyway, your new version is of course also only O(n^2).


  • 0
    V

    I am finding it hard to make it O(N) without an extra list ... the modifying using slice was not going very well with submission ... now i have two list .. and never use remove or pop .. append offcource is O(N) but then addition of two list without reference is another O(N), this time though outside the loop ...


  • -1
    M
    This post is deleted!

  • 0
    V

    nums.pop(i) is O(n) .. making the solution O(n^2) ...


Log in to reply
 

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