6-10PM challenge problem #001

#challenge #programming #problem #interview

akbhairwal Sep 24, 2019 ・1 min read

Move Zeros To End

An array 'arr' which have integers. You need to move all the zeros in the end of the array. You should preserve the relative order of other numbers in the array.

We should implement a solution that is more efficient than a naive brute force.

Example :
Given array arr = [12, 3, 0, 2, 8, 11, 0, 0, 6, 4, 0, 5, 7, 0, 8, 9, 0]
output: [12, 3, 2, 8, 11, 6, 4, 5, 7, 8, 9, 0, 0, 0, 0, 0, 0]

Solution

Discussion

Brad • Sep 25 '19

This is my "code-golf-esque" solution.

const arr = [12, 3, 0, 2, 8, 11, 0, 0, 6, 4, 0, 5, 7, 0, 8, 9, 0];

const combine = ({ nums, zeros }) => [...nums, ...zeros];
const moveZeroes = arr =>
  combine(
    arr.reduce(
      (acc, num) =>
        (num === 0 ? acc.zeros.push(num) : acc.nums.push(num)) && acc,
      {
        nums: [],
        zeros: []
      }
    )
  );

console.log(moveZeroes(arr));

I wasn't to sure about what the "naive brute force" is. My current solution should always run at 2n where n is the number of integers in the array, this assumes the combine method just iterates the two arrays together.

I'm 100% sure there is a 1n approach, where you iterate over the array only 1 time, but I personally hate working on arrays I'm iterating over.

edit I didn't see this was tagged as a Java problem, and the above is JavaScript, so it is what it is haha.

akbhairwal • Sep 25 '19

oh Sorry... I should make it language independent..
I think it can be done in single array iteration and having two pointer for swapping

Oleksii Filonenko • Sep 25 '19

Rust, my best shot at performance (checked with benchmarks):

pub fn move_zeros_to_end_deque(nums: &[i32]) -> VecDeque<i32> {
    let mut deque = VecDeque::with_capacity(nums.len());
    for &n in nums.into_iter().rev() {
        if n == 0 {
            deque.push_back(n);
        } else {
            deque.push_front(n);
        }
    }
    deque
}

Benserya • Sep 25 '19

did u try the given array in ur solution?

Gab • Sep 29 '19

O(n) Clojure solution:

(defn move-zeros [arr]
  (loop [lst arr 
         nonzeros []
         zeros []]
    (cond
      (empty? lst) (concat nonzeros zeros)
      (= (first lst) 0) (recur (rest lst) nonzeros (conj zeros 0))
      :else (recur (rest lst) (conj nonzeros (first lst)) zeros))))

(move-zeros [12 3 0 2 8 11 0 0 6 4 0 5 7 0 8 9 0])
;; (12 3 2 8 11 6 4 5 7 8 9 0 0 0 0 0 0)

EarlWare • Sep 26 '19

Swift solution:

import Foundation

/*
 6-10PM Challenge part 1

@param mixedArray is a ordered list of Ints with zeros mixed in randomly.

 @return the same list of Ints with order preserved, except that all the zeros have been moved to the end.
 */
func zerosToEnd(mixedArray:[Int]) -> [Int] {
    return mixedArray.filter({ $0 != 0})+mixedArray.filter({ $0 == 0})
}


let example1 = [12, 3, 0, 2, 8, 11, 0, 0, 6, 4, 0, 5, 7, 0, 8, 9, 0]
let solution1 = [12, 3, 2, 8, 11, 6, 4, 5, 7, 8, 9, 0, 0, 0, 0, 0, 0]


print(zerosToEnd(mixedArray: example1), "\n")
print("Testing example1 matches solution1:     ", (zerosToEnd(mixedArray: example1) == solution1), "\n\n")

Output:

[12, 3, 2, 8, 11, 6, 4, 5, 7, 8, 9, 0, 0, 0, 0, 0, 0] 

Testing example1 matches output1:      true 


Program ended with exit code: 0

I opted to just filter out all the zeros entirely/filter everything but zeros, then recombine in the correct order.

DEV Community

DEV Community is a community of 553,164 amazing developers

6-10PM challenge problem #001

Discussion

Read next

Cool Extensions for VS Code

Stop Memorizing! : The #1 Advice I Wish Someone Would Have Told Me

Advent of Code 2020: Python Solution Day 19

Advent of Code 2020 Solution Megathread - Day 15: Rambunctious Recitation