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

    Ugly Haskell:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: