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

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 2

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 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

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 9

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 10

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 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.

Answer 12

`def move_zeros(listn):
     n = [number for number in listn if isinstance(inumber, bool) or number!=0]
     listn = n + [0]*(len(listn)-len(n))
     return listn`

Answer 13

Naïve Benchmarks

In place
     gboffi1|   727.3899 μs,   729.9263 μs,   730.8136 μs,   731.3269 μs,   733.5562 μs
     gboffi2| 19271.8119 μs, 19280.2418 μs, 19290.8053 μs, 19684.0108 μs, 20424.9170 μs
     gboffi3|  8867.9423 μs,  8871.5615 μs,  8875.3720 μs,  8876.5216 μs,  8879.1700 μs
        Cabu|   822.5495 μs,   835.4780 μs,   835.7711 μs,   844.2948 μs,   853.0149 μs
      joanis|   506.0253 μs,   506.1155 μs,   506.1627 μs,   506.1810 μs,   506.5230 μs
      Soumya|  1203.9832 μs,  1206.2782 μs,  1208.5386 μs,  1245.2450 μs,  1254.6893 μs
Copying
     gboffi4|   414.7999 μs,   418.4400 μs,   418.5836 μs,   418.7423 μs,   418.7452 μs
      Ilya_1|   524.9701 μs,   525.1853 μs,   526.0796 μs,   526.6274 μs,   526.9053 μs
      Ilya_2|   306.7650 μs,   306.8397 μs,   307.0605 μs,   307.1060 μs,   307.3800 μs
      Ilya_3|   308.0310 μs,   311.2493 μs,   311.8763 μs,   314.4209 μs,   321.3265 μs
       Timur|   406.5968 μs,   406.6816 μs,   406.8116 μs,   406.9451 μs,   407.1210 μs

Copying is faster than working in place.

If copying, the simpler, the faster and, list comprehensions are the real thing.

Working in place, it seems to me that

• the easy optimizations used by joanis make a difference,
• my method no. 1 is rather fast and quite simple, and
• it's easy to incur in abysmal performance (my code no. 2 and no.3).

If you think that some code is misrepresented in my implementation, I'll be glad to correct any issue.

from random import randint, seed
from timeit import Timer

def timer(stmt):
    tmr = Timer(stmt, globals=globals())
    n, *t = tmr.autorange()
    t += tmr.repeat(number=n, repeat=4)
    return sorted([t_i/n for t_i in t])
def print_times(name, stmt):
    print("%12s|"%name,
          ', '.join("%10.4f μs"%(1E6*t_i) for t_i in timer(stmt)))

seed(20230326)
l = [randint(0, 20) for _ in range(10_000)]

def gboffi2(l, c=0):
    while True:
        try:
            l.remove(0)
            c += 1
        except ValueError:
            break
    l += [0]*c
def gboffi3(l):
    for i in reversed([i for i, v in enumerate(l) if v==0]): l[i:] = l[i+1:]+[0]
def gboffi4(l):
    for i in reversed([i for i, v in enumerate(l) if v==0]): l = l[i:]+l[i+1:]+[0]
def Soumya(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
def Cabu(nums):
    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)
def Ilya3(l): return [x for x in l if x !=0]+[0]*l.count(0)
def joanis(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
def Timur(l):
    l = [x for x in l if x != 0 ] + [x for x in l if x == 0 ]

print("In place")
print_times('gboffi1',  'l[::].sort(key = lambda n:n==0)')
print_times('gboffi2',  'gboffi2(l[::])')
print_times('gboffi3',  'gboffi3(l[::])')
print_times('Cabu',     'Cabu(l[::])')
print_times('joanis',   'joanis(l[::])')
print_times('Soumya' ,  'Soumya(l[::])')
print("Copying")
print_times('gboffi4',  'gboffi4(l[::])')
print_times('Ilya_1',   'a=list(filter(lambda x: x!= 0, l))+[0]*l.count(0)')
print_times('Ilya_2',   'a=[x for x in l if x !=0]+[0]*l.count(0)')
print_times('Ilya_3',   'a=Ilya3(l[::])')
print_times('Timur',    'a=[x for x in l[::] if x!=0 ]+[x for x in l[::] if x== 0]')