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.
Programming Praxis 
Simple solution using two passes.
One pass solution
Ugly Haskell:
Java
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:])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_().
Very simple solution in C
Simple Haskell linear cost:
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]
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.
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]
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.
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.
Jussi gets the gold star! We discussed the Dutch National Flag problem in a previous exercise.
@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 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 xsjava
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};
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};
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};
I forgot the last case:
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)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])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;
}
}
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 cntGiven an array `a`, to move all zeroes to the right, do this (in Ruby):
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:
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:
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]
Python:
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:
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.
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.
import Data.Array.IO import Control.Monad 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 lSimple 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]))
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();
}