## An Array Of Zeroes

### November 21, 2014

Before you look at the suggested solution, check what yours does when given an empty array, an array containing only zeroes, or an array containing only non-zeroes.

We keep two indices: `lo` is the lowest unexamined index, `hi` is the highest unexamined index. Then we iterate. If the item at the current `lo` is zero, we swap it with the item at the current `hi` and move `hi` to the left. Otherwise, we move `lo` to the right and add 1 to the counter. Iteration stops when the two pointers cross:

```(define (zeroes vec)   (let loop ((lo 0) (hi (- (vector-length vec) 1)) (counter 0))     (cond ((< hi lo) (values counter vec))           ((zero? (vector-ref vec lo))             (vector-set! vec lo (vector-ref vec hi))             (vector-set! vec hi 0)             (loop lo (- hi 1) counter))           (else (loop (+ lo 1) hi (+ counter 1))))))```

Here are some examples:

```> (zeroes '#(1 0 2 3 0 0 4)) 4 #(1 4 2 3 0 0 0) > (zeroes '#(1 1 1 1 1)) 5 #(1 1 1 1 1) > (zeroes '#(0 0 0 0 0) 0 #(0 0 0 0 0) > (zeroes '#(0 0 1 2 3 4 0 0)) 4 #(4 3 1 2 0 0 0 0)```

You may notice that this program is similar to a previous exercise, or to the partitioning step of quick sort. This is another good interview question, similar to the one we had a few weeks ago: it looks simpler than it actually is, thus giving you a chance to compare candidates on whether or not they recognize and deal with the complexity.

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_)
```

```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 Control.Monad.ST
import Data.Array.ST

zeroSort xs = let reorder i j = do
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
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
```

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

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
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();
}