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

Simple solution using two passes.

One pass solution

Ugly Haskell:

Java

In Python.

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

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

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.

publicclassArrayOfZeros {publicint[] moveNonZeroElementsToLeft(int[] array) {for(inti = 0; i < array.length; i++) {if(array[i] == 0) {moveNonZeroElements(array, i);

}

}

returnarray;}

privatevoidmoveNonZeroElements(int[] array,inti) {for(intj = 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};

zArr :: (Num a) => [a] -> [a]

zArr [] = []

zArr (0:xs) = zArr xs ++ [0]

I forgot the last case:

zArr (x:xs) = x : zArr xs

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

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

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;

}

}

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

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:

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.

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

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

}