Python Forum

Question is:

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

   You must do this in-place without making a copy of the array.
   Minimize the total number of operations.

My code has passed a simple case, but failed an extreme case which has the fifth last element as 0. I don't know where is the loophole in my code.

L

Here is my code:

class Solution(object):
    def moveZeroes(self, nums):
        i=0
        Count=0
        ZeroCount=0
        MaxCount=(len(nums)-ZeroCount)
        print("Input Size=",len(nums))
        while Count <MaxCount-ZeroCount:
            Count=Count+1
            if nums[i]==0:
               nums.pop(i)
               nums.append(0)
               ZeroCount=ZeroCount+1
               i=i-1
            i=i+1
        return nums    


print(Solution().moveZeroes([0,1,0,3,12]))
print(Solution().moveZeroes([-959151711,623836953,209446690,-1950418142,1339915067,-733626417,481171539,-2125997010,-1225423476,1462109565,147434687,-1800073781,-1431212205,-450443973,50097298,753533734,-747189404,-2070885638,0,-1484353894,-340296594,-2133744570,619639811,-1626162038,669689561,0,112220218,502447212,-787793179,0,-726846372,-1611013491,204107194,1605165582,-566891128,2082852116,0,532995238,-1502590712,0,2136989777,-2031153343,371398938,-1907397429,342796391,609166045,-2007448660,-1096076344,-323570318,0,-2082980371,2129956379,-243553361,-1549960929,1502383415,0,-1394618779,694799815,78595689,-1439173023,-1416578800,685225786,-333502212,-1181308536,-380569313,772035354,0,-915266376,663709718,1443496021,-777017729,-883300731,-387828385,1907473488,-725483724,-972961871,-1255712537,383120918,1383877998,1722751914,0,-1156050682,1952527902,-560244497,1304305692,1173974542,-1313227247,-201476579,-298899493,-1828496581,-1724396350,1933643204,1531804925,1728655262,-955565449,0,-69843702,-461760848,268336768,1446130876]))

Output is:

Quote:Input Size= 5
[1, 3, 12, 0, 0]
Input Size= 100
[-959151711, 623836953, 209446690, -1950418142, 1339915067, -733626417, 481171539, -2125997010, -1225423476, 1462109565, 147434687, -1800073781, -1431212205, -450443973, 50097298, 753533734, -747189404, -2070885638, -1484353894, -340296594, -2133744570, 619639811, -1626162038, 669689561, 112220218, 502447212, -787793179, -726846372, -1611013491, 204107194, 1605165582, -566891128, 2082852116, 532995238, -1502590712, 2136989777, -2031153343, 371398938, -1907397429, 342796391, 609166045, -2007448660, -1096076344, -323570318, -2082980371, 2129956379, -243553361, -1549960929, 1502383415, -1394618779, 694799815, 78595689, -1439173023, -1416578800, 685225786, -333502212, -1181308536, -380569313, 772035354, -915266376, 663709718, 1443496021, -777017729, -883300731, -387828385, 1907473488, -725483724, -972961871, -1255712537, 383120918, 1383877998, 1722751914, -1156050682, 1952527902, -560244497, 1304305692, 1173974542, -1313227247, -201476579, -298899493, -1828496581, -1724396350, 1933643204, 1531804925, 1728655262, -955565449, 0, -69843702, -461760848, 268336768, 1446130876, 0, 0, 0, 0, 0, 0, 0, 0, 0]

I highlighted the 0 in red that is missed by the expected operation.

Not positive where the error is in your current (likely some index issue) but if you simplify it a bit it works fine.  Note however it is a O(n^2) solution.

class Solution(object):
    def moveZeroes(self, nums):
        i = 0
        moved = 0
        zero_count = nums.count(0)
        while moved < zero_count:
            if nums[i] == 0:
               nums.pop(i)
               nums.append(0)
               moved += 1
               continue
            i += 1
        return nums

I prefer this, though I almost guarantee your teacher will hate it:  

nums.sort(key=lambda x: x == 0)

Why work harder when you can work smarter?

(Jan-22-2017, 04:40 AM)Mekire Wrote: [ -> ]Why work harder when you can work smarter?

I wrote a linear time, constant space solution in 10 lines. Not sure if Python's sorting is linear time in this case (and not sure about space); it might be optimal.

That said, working harder for quadratic time is definitely not ideal :)

landlord1984: your teacher probably wouldn't find quadratic time acceptable based on the "Minimize the total number of operations" comment. If efficiency has been discussed in your coursework, you should probably figure out an O(n) solution. O(n log n) might be acceptable, though they might not be thrilled by Mekire's clever solution, especially if you didn't come up with it yourself.

(Jan-22-2017, 04:40 AM)Mekire Wrote: [ -> ]I prefer this, though I almost guarantee your teacher will hate it:  

nums.sort(key=lambda x: x == 0)

I can't understand why the zeroes goes at the right

By sorting on key x == 0 we are sorting two values; True and False. True is greater than False so they appear to the right. The other numbers don't change order because timsort is a stable sort.

Techniclally you don't need to sort... all the zero values are undistinguishable from each other. So:

nums=[....] # whaetever
nozeroes=[x for x in nums if x!=0] # everything but zeroes
final=nozeroes+[0]*(len(nums)-len(nozeroes)) # add required zeroes back

That violates the requirements.

He needs to write the algorithm to operate inplace.
Making a copy of any kind is against the rules.

It can be argued that using sort violates this rule as well as it is likely not constant space for this (and certainly isn't in general) but that is hard to test.

Ideally as Mic said he needs to write a linear time complexity constant space algorithm.

i=0
num=[]
class sorter():
        def sortzeroes(num):
             for i in num:
                  if num[i]==0:
                     num.pop(i)#i dont really know what pop do ,so this code may not work
                     num.append(0)
             print(num)        
             

have not tested it yet,not sure it works

If that worked, which as it is written it does not, it would still be a O(n^2) solution.

(I deleted a solution that someone provided that may have been doing the OP's homework for them. The poster may have thought it was alright because it was an improvement on the OP's solution in some sense, but because the assignment suggests it should be fully efficient, and the OP hasn't gotten there yet, I thought it was best to delete.)