Move all zeros to the end of the array in python

Question

Given an array nums, I am trying to move all 0's to the end of it while maintaining the relative order of the non-zero elements. I am trying to do this in-place without making a copy of the array.

So for input [0,1,0,3,12], output should be [1,3,12,0,0]. But my code below is only able to move the first zero in the array to the end of the array and gives the wrong output of [1,0,3,12,0]. How can I modify it so that all zeros move to the end of the array efficiently?

class Solution:
def moveZeroes(self, nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    n=len(nums)
    for i in range(0,n):
        if (nums[i]==0) and ((i+1)<n): 
            nums[i]=nums[i+1]
            nums[i+1]=0
            print(nums) 

Answer 1

Let me do your homework :-)

n = len(nums)
j = 0
for i in range(n):
    nums[j] = nums[i]
    j += 1 if nums[i] else 0
nums[j:] = [0] * (n-j)

If you bang your head enough to understand it, you will have at least learn something...

Answer 2

Python's built-in sort is a stable sort, meaning that elements are exchanged only when they are different according to the criteria you use for sorting.

To use sort to move all the zeros to the end, we have to find a transform for which a zero is always greater than any other value, but this is easy... Python booleans are ordered and True is greater than False, so our magic transformation is simply n==0!

Demonstration:

In [1]: sorted([0,1,0,3,12], key=lambda n: n==0)
Out[1]: [1, 3, 12, 0, 0]

If you want to avoid a copy, use the .sort method of lists.

l = [0,1,0,3,12]
l.sort(key=lambda n:n==0)

Answer 3

Two Pointers Algorithm

Here is the solution with O(N) time complexity with no auxiliary space.

def move_zeros(data: list) -> list:
    size = len(data)
    left = right = 0
    while right < size:
        if data[right] == 0:
            right += 1
        else:
            data[left], data[right] = data[right], data[left]
            right += 1
            left += 1
    return data


if __name__ == "__main__":  
    arr = [1, 2, 0, 0, 3, 4, 0, 0, 0, 7, 2, 4]
    print(move_zeros(data=arr))

Output:

[1, 2, 3, 4, 7, 2, 4, 0, 0, 0, 0, 0]

Answer 4

list(filter(lambda x: x!= 0, array))+[0]*array.count(0)

or

[x for x in array if x !=0]+[0]*array.count(0)

Answer 5

Your issue is that, after the first step, you have two zeros next to each other. You swap the zeros, then leave the 0 in the [1] position in-place, never making it to the back

Instead, I recommend you iterate the array and keep a tracker of the last non-zero number, j, initialised as -1. You can swap any non-zeros you encounter to j+1. The order of the 0s afterwards doesn't matter.

Side note: in python, range(n) will iterate 0 -> n-1, so you shouldn't need the 2nd conditional in the and statement to terminate the loop. Instead you could do range(n-1), for example

Answer 6

Use list comprehensions to partition the list into 2 lists, then concatenate them in the desired order:

orig_lst = [0, 1, 0, 3, 12]
lst_non0 = [x for x in orig_lst if x != 0 ]
lst_0    = [x for x in orig_lst if x == 0 ]
lst_0s_at_end = lst_non0 + lst_0
print(lst_0s_at_end)
# [1, 3, 12, 0, 0]

You can also achieve the same result by changing the original list in-place:

orig_lst = [0, 1, 0, 3, 12]
orig_lst = [x for x in orig_lst if x != 0 ] + [x for x in orig_lst if x == 0 ]

Answer 7

One could just remove the zeros, while at the same time counting them, and later append to the remaining of the original list how many zeros as we previously removed...

>>> help(list.remove)
Help on method_descriptor:

remove(self, value, /)
    Remove first occurrence of value.
    
    Raises ValueError if the value is not present.
>>> import random
>>> c, l = 0, [random.randint(0, 10) for _ in range(100)]
>>> while True:
...     try:
...         l.remove(0)
...         c += 1
...     except ValueError:
...          break
>>> l += [0]*c

Answer 8

The idea is to remove all the occurrences of zeros in the list using remove function and maintain a count variable to count the number of occurrences of zero and at the end append zero "count" many times.I hope this is efficient solution for your problem.Please find the code for the same:

lis = [1,2,0,5,6,0,6,0,7]
count = 0
for i in lis:
   if(i==0):
      lis.remove(i)
      count = count+1
for i in range(count):
   lis.append(0)
print(lis)

Answer 9

The array can be sorted using the sorted function of python keeping reversed as True. the second method is also given there.

# one way
array42 = [0, 5, 2,0,0,5,2,7,0,2,3]
print(sorted(array42))


# second way
index = len(array42)-1
for i in range(len(array42)-1,-1,-1):
    if array42[i]!=0:
        array42[index]=array42[i]
        index -= 1

for i in range(index,-1,-1):
    array42[index]=0
    index -= 1
print(array42)

Answer 10

Another way to approach this problem: (working backward - it also can be applied to general case when iterating and processing, normally it's NOT recommended). Time wise comparison - @gboffi is better O(log N), and this one is O(N).

def moveZeros(A):
    for i in range(len(A)-1, -1, -1):
        if not A[i]:       # num. is 0
           del A[i]
           append(0)
      

Answer 11

This question has enough answers, I'm not sure why I feel compelled to add yet another, but I am. My solution is fundamentally equivalent to @Cabu's, based on the realization that you don't need to store those 0's you're moving, since they're all the same. Instead, you can overwrite them as you loop once over the array, and write the correct number of zeros at the end.

def moveZeroes(nums) -> None:
    pos = 0  # keep track of where to place the next non-zero value
    for num in nums:
        if num != 0:
            nums[pos] = num
            pos += 1
    for i in range(pos, len(nums)):
        nums[i] = 0

I'm posting this additional solution because

• I prefer minimizing the use of indices: use for num in nums: instead of for i in range(n):.
• I'm avoiding creating a temporary list of 0's with my second loop.

So this solution might be (untested claim, but at least trivially) more efficient: this code runs in linear time and requires no additional storage.

All that being said, if the "zero" values had to be preserved because they were different in some way, my preferred solution would be the two pointer algorithm presented by @Soumya. It also runs in linear time and avoids any temporary storage. It shuffles those zeros, though, so if the order of the zeros was to matter, it wouldn't work as is.