## An Array Of Zeroes

### November 21, 2014

Beware! Today’s exercise, which derives from an interview question asked at Facebook, is trickier than it looks:

You are given an array of integers. Write a program that moves all non-zero integers to the left end of the array, and all zeroes to the right end of the array. Your program should operate in place. The order of the non-zero integers doesn’t matter. As an example, given the input array [1,0,2,0,0,3,4], your program should permute the array to [1,4,2,3,0,0,0] or something similar, and return the value 4.

Your task is to write the indicated program. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 31 Responses to “An Array Of Zeroes”

1. Carlos Vázquez said

Simple solution using two passes.

2. Francesco said

g ns = foldr (\n (r,c) -> if n==0 then (r++[n],c) else (n:r,c+1)) ([],0) ns
3. Paul said

In Python.

def zeros(arr):
n = len(arr)
left, right = 0, n - 1
while 1:
while left  < n  and arr[left]  != 0: left  += 1
while right >= 0 and arr[right] == 0: right -= 1
if left >= right: break
arr[left], arr[right] = arr[right], arr[left]
return left

# test it
from random import choice, uniform

for i in range(100):
arr = [choice([0,1]) for _ in range(20)]
arr2 = list(arr)
n = zeros(arr2)
assert n == len([a for a in arr if a !=0])
assert all(a for a in arr2[:n])
assert all(a == 0 for a in arr2[n:])

4. Mike said

Keeping it simple: use the built in sort(), with a key that returns True (i.e. 1) for elements == 0 and returns False (i.e. 0) otherwise: op.not_().

import operator as op

x.sort(key=op.not_)

5. Simple Haskell linear cost:

filter (>0) xs ++ filter (<1) xs

6. Haskell one pass solution (may be modified for any condition, not only zeros):

z [] zs = zs
z (0:xs) zs = z xs (0:zs)
z (x:xs) zs = x: z xs zs
[/source]

7. Mike said

I’m not very familiar with Haskell do the solutions operate “in place” or do they return a new list? What about the Lisp solution? I thought functional languages generally have immutable variables.

8. Lorenzo said

A solution in Perl:

#!/usr/bin/env perl

use strict;
use warnings;

my \$a = [1,0,2,0,0,3,4];

my (\$i, \$j) = (0, \$#\$a);

#
# Invariants
# 1 – no zero before position \$i
# 2 – no non-zero after position \$j
#

while (\$i [\$j] == 0) { # invariant 2 still holds if we decrease \$j
\$j–;
} elsif (\$a->[\$i] != 0) { # invariant 1 still holds if we increase \$i
\$i++;
} else {
\$a->[\$i] = \$a->[\$j];
\$a->[\$j] = 0; # we know \$a[\$i] was zero
\$j–; # both invariants will still hold due to the “swap”
\$i++;
}
}

print “non-zero elements = \$i\n”;
print “resulting array = [” . join(‘,’, @\$a). “]\n”;
[\code]

9. Jussi Piitulainen said

I like a stable in-place sort best. It keeps the order within groups, and it generalizes naturally to more groups. Incidentally, several solutions don’t really swap but store a literal zero to a right-end position. This makes a difference if there are different zeroes, as in the following Python.

>>> x = [3, 0, 1, 4, 1.0, 5, 9, 0, 0.0, 0, 2, 6]
>>> x.sort(key=lambda i: i == 0)
>>> x
[3, 1, 4, 1.0, 5, 9, 2, 6, 0, 0, 0.0, 0]
>>>

On the other hand, if all zeroes are the same, it’s easy to keep the non-zeroes in order by tracking the end of the left block while scanning the array, copying each non-zero to its place, and finally zeroing out the right block. A scan and a half, as it were, though two full scans in the worst case of all zeroes.

But there actually is a single-pass algorithm for sorting red, white, and blue numbers into three blocks, isn’t there? Dijkstra’s national flag or something? Lazy/busy to look it up now.

10. programmingpraxis said

Jussi gets the gold star! We discussed the Dutch National Flag problem in a previous exercise.

11. @Mike, you are right, here is other one (single pass) using mutable array in a pure way (ST monad):

import Data.Array.ST

zeroSort xs = let reorder i j = do
u <- read i
v <- read j
if      i >= j then return ()
else if u /= 0 then reorder (i + 1) j
else if v == 0 then reorder i (j - 1)
else                swap i j
in  getBounds xs >>= uncurry reorder

-- helpers
where read i    = readArray  xs i
write i v = writeArray xs i v
swap i j  = do { u <- read i; v <- read j; write i v; write j u }

testZeroSort = runST \$ do
xs <- newListArray (0, 5) [0..5] :: ST s (STArray s Int Int)
zeroSort xs
getElems xs

12. Rahul Chandna said

java
public class ArrayOfZeros {

public int[] moveNonZeroElementsToLeft(int[] array) {
for (int i = 0; i i – 1; j–) {
if (array[j] != 0) {
array[i] = array[j];
array[j] = 0;
break;
}
}
}
}

Test cases
int array[] = {1, 0, 2, 0, 0, 3, 4};
int expectedOutput[] = {1, 4, 2, 3, 0, 0, 0};

int array[] = {0, 0, 1, 5, 6, 8, 0, 0};
int expectedOutput[] = {8, 6, 1, 5, 0, 0, 0, 0};

int array[] = {0, 0, 0, 0, 0, 0, 0};
int expectedOutput[] = {0, 0, 0, 0, 0, 0, 0};

int array[] = {1, 1, 1, 1, 1};
int expectedOutput[] = {1, 1, 1, 1, 1};

13. Rahul Chandna said

java
public class ArrayOfZeros {

public int[] moveNonZeroElementsToLeft(int[] array) {
for (int i = 0; i i – 1; j–) {
if (array[j] != 0) {
array[i] = array[j];
array[j] = 0;
break;
}
}
}
}

Test cases
int array[] = {1, 0, 2, 0, 0, 3, 4};
int expectedOutput[] = {1, 4, 2, 3, 0, 0, 0};

int array[] = {0, 0, 1, 5, 6, 8, 0, 0};
int expectedOutput[] = {8, 6, 1, 5, 0, 0, 0, 0};

int array[] = {0, 0, 0, 0, 0, 0, 0};
int expectedOutput[] = {0, 0, 0, 0, 0, 0, 0};

int array[] = {1, 1, 1, 1, 1};
int expectedOutput[] = {1, 1, 1, 1, 1};

14. Rahul Chandna said

Sorry for the spam, I didn’t read the howto section first so my code was not displaying correctly.

public class ArrayOfZeros {

public int[] moveNonZeroElementsToLeft(int[] array) {
for (int i = 0; i < array.length; i++) {
if (array[i] == 0) {
moveNonZeroElements(array, i);
}
}
return array;
}

private void moveNonZeroElements(int[] array, int i) {
for (int j = array.length - 1; j > i - 1; j--) {
if (array[j] != 0) {
array[i] = array[j];
array[j] = 0;
break;
}
}
}
}
Code Formatted by ToGoTutor

Test cases
int array[] = {1, 0, 2, 0, 0, 3, 4};
int expectedOutput[] = {1, 4, 2, 3, 0, 0, 0};

int array[] = {0, 0, 1, 5, 6, 8, 0, 0};
int expectedOutput[] = {8, 6, 1, 5, 0, 0, 0, 0};

int array[] = {0, 0, 0, 0, 0, 0, 0};
int expectedOutput[] = {0, 0, 0, 0, 0, 0, 0};

int array[] = {1, 1, 1, 1, 1};
int expectedOutput[] = {1, 1, 1, 1, 1};

15. John Lekberg said
zArr :: (Num a) => [a] -> [a]
zArr []     = []
zArr (0:xs) = zArr xs ++ [0]

16. John Lekberg said

I forgot the last case:

zArr (x:xs) = x : zArr xs

17. matthew said

Clojure solution using a Java array so the partition really is in-place:

(defn part [f]
(fn [a]
(loop [i 0
j (- (alength a) 1)]
(when (> j i)
(cond (not (f (aget a i)))
(recur (+ i 1) j)
(f (aget a j))
(recur i (- j 1))
:else
(let [t (aget a i)]
(aset a i (aget a j))
(aset a j t)
(recur (+ i 1) (- j 1))))))))

(def zeropart (part #(= % 0)))

(def a (to-array [1 0 2 0 0 3 0 4 5 0]))
(zeropart a )
(vec a)

18. matthew said

Alternatively, we can use Clojure transients (a sort of local mutable copy of an immutable object);

(defn part [f]
(fn [s]
(loop [a (transient s)
i 0
j (- (count a) 1)]
(if (<= j i)
(persistent! a)
(cond (not (f (a i)))
(recur a (+ i 1) j)
(f (a j))
(recur a i (- j 1))
:else
(let [ai (a i)
aj (a j)]
(recur (assoc! (assoc! a i aj) j ai)
(+ i 1) (- j 1))))))))

(def zeropart (part #(= % 0)))
(zeropart [1 0 2 0 0 3 0 4 5 0])

19. klettier said

var tab = new short[]{1,0,2,0,0,3,4,5,89,0,5,9,0,1};
tab = tab.OrderBy(s => s == 0 ? 1 : 0).ToArray();

or

var tab = new short[]{1,0,2,0,0,3,4,5,89,0,5,9,0,1};
short firstZeroIndex = -1;

for(short i = 0; i < tab.Length; i++)
{
if(tab[i] != 0 && firstZeroIndex != -1)
{
short a = tab[i];
tab[i] = tab[firstZeroIndex];
tab[firstZeroIndex] = a;

firstZeroIndex++;
}
else if(tab[i] == 0 && firstZeroIndex == -1)
{
firstZeroIndex = i;
}
}

20. Mark said
def zeros_to_end(ar):
cnt, write_loc = 0, 0
for i, n in enumerate(ar[:]):
if n != 0:
cnt += 1
ar[i] = 0
ar[write_loc] = n
write_loc += 1
return cnt

21. Alan S. said

Given an array `a`, to move all zeroes to the right, do this (in Ruby):

a.sort.reverse

If you want a little program that will read a list of numbers and produce the list with the zeroes moved to the right:

#!/usr/bin/env ruby
# mv-zeroes.rb
puts ARGF.read.split(' ').sort.reverse.join(' ')

Now, let’s run the little script:

\$ echo 1 2 0 0 3 4 5 9 0 | mv-zeroes.rb
9 5 4 3 2 1 0 0 0

Now, if you wanted to keep the original sequence of integers, and/or do the zero-moving in-place, here’s how:

#!/usr/bin/env ruby
# mv-zeroes2.rb
class Array
def move_zeroes()
a = self
x = y = 0
l = a.length
while x < l
if a[x].to_i == 0
x += 1
next
elsif y < x
a[y] = a[x]
end
x += 1
y += 1
end
while y < l
a[y] = 0
y += 1
end
a
end
end
puts ARGF.read.split(' ').move_zeroes.join(' ')

And the sample run:

\$ echo 1 2 0 0 9 8 5 7 0 | mv-zeroes2.rb
1 2 9 8 5 7 0 0 0

22. aks said

Here is an implementation using elixir. It uses the same “reverse on top of sort” trick, which is not in-place, but it’s built-in to the language.
[codesource lang=”elixir”]
#!/usr/bin/env elixir
import Enum
IO.puts inspect(reverse(sort(map(String.split(IO.gets “”), fn(x) -> elem(Integer.parse(x),0) end))))
[/codesource]

And the sample run:

[codesource lang=”bash”]
\$ echo 3 4 0 6 4 0 0 2 8 6 0 5 | t.exs
[8, 6, 6, 5, 4, 4, 3, 2, 0, 0, 0, 0]
[/codesource]

Because elixir is built on top of erlang, it doesn’t have traditional loops; instead it uses functional programming techniques, including recursion to accomplish iterations across collections.

Here’s an implementation more in the spirit of this quiz, but using elixir recursion to build up a new list that has the zeroes moved to the right:

[codesource lang=”elixir”]
#!/usr/bin/env elixir
import Enum
defmodule Fun do
def move_zeroes([f|r]) when f != 0 do
[f] ++ move_zeroes(r)
end
def move_zeroes([f|r]) when f == 0 do
move_zeroes(r) ++ [0]
end
def move_zeroes([]) do
[]
end
end
IO.puts inspect(Fun.move_zeroes(map(String.split(IO.gets “”), fn(x) -> elem(Integer.parse(x),0) end)))
[/codesource]

Here’s the output:

[codesource lang=”bash”]
\$ echo 3 4 0 6 4 0 0 2 8 6 0 5 | t2.exs
[3, 4, 6, 4, 2, 8, 6, 5, 0, 0, 0, 0]
[/codesource]

23. Chippiewill said

Python:

lst = [1,0,2,0,0,3,4]
n = 0
z = len(lst)-1

while(n < z):

if(lst[n] == 0):
lst[n], lst[z] = lst[z], lst[n]
z -= 1
else:
n += 1
print lst

24. Alex M. said

Pfff… the quantity of nonsense in many of the above answers is worrysome. Are you, people, programming for a living? If so, then I hope to never have to use your software products. One mistake that many made was to ignore the requirement of the problem: the sorting must be done *in place*. This rules out many Haskell one-liners and makes the problem tricky.

Alan S., are you sure that your Ruby program works when you have non-negative integers in your array?

Now, assume that we have some Scheme procedure that sorts an array of integers in place, called “sort”, that takes 2 arguments: an order (a boolean predicate) and an array to be sorted. Next, define a new order relationship (called “lessthan”) on the integers: a lessthen b iff b=0 (this simply makes 0 the largest integer). (Note that it is reflexive, antisymmetrical and transitive.) Let “array” be the array of integers to be sorted. The following code does the job:

(define (lessthan a b) (zero? b))
(sort lessthan array)

Any sorting algorithm may be used, nut just quicksort (used in the “official” answer), as long as it accepts the order (predicate) as an argument.

25. Alex M. said

By the way, the code snippet above does not count the number of non-zero elements. Most of the code snippets above don’t, either.

26. svenningsson said
import Data.Array.IO

zsort arr = do (i,j) <- getBounds arr
sort arr 0 i j

sort arr acc i j | j < i = return acc
sort arr acc i j =
do a <- readArray arr i
if a /= 0 then sort arr (acc + 1) (i+1) j else do
b <- readArray arr j
if b == 0 then sort arr acc i (j-1) else do
writeArray arr i b
writeArray arr j a
sort arr (acc+1) (i+1) (j-1)

test = do arr <- newListArray (1,7) [1,0,2,0,0,3,4] :: IO (IOUArray Int Int)
n <- zsort arr
print n
l <- getElems arr
print l

27. Brett Warren said

Simple in-place solution, coded in Python. Best case O(n), worst case O(n^2).

from itertools import islice

def zeros_sort(int_list):
for i, num1 in enumerate(int_list):
if not num1:
for l, num2 in islice(enumerate(int_list), i, None):
if num2:
int_list[i], int_list[l] = int_list[l], int_list[i]
return int_list

if __name__ == “__main__”:
print(zeros_sort([1,0,2,0,0,3,4]))

28. Anish Sharma said

Well, in C, the following code works.
#include
#include
void main()
{
int ar[20];
int i,b,max,cb=0,count=0,n=19,temp,nf,c;
clrscr();
for(i=0;i<=n;i++)
{
scanf("%d",&ar[i]);
if(ar[i]!=0)
count++;
}
max=n;
for(b=0;b<=count-1;b++)
{
if(ar[b]==0 && cb<count)
{
if(ar[max]!=0)
{
temp=ar[max];
ar[max]=ar[b];
ar[b]=temp;
max=max-1;
cb++;
}
else
{
max=max-1;
b=b-1;
continue;
}
}

}

for(i=0;i<=n;i++)
{
printf(" %d",ar[i]);
}
getch();
}