DEV Community

akbhairwal
akbhairwal

Posted on

6-10PM challenge problem #001

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

Top comments (6)

Collapse
 
bradtaniguchi profile image
Brad • Edited

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.

Collapse
 
akbhairwal profile image
akbhairwal

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

Collapse
 
brightone profile image
Oleksii Filonenko

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
}
Collapse
 
benserya profile image
Benserya

did u try the given array in ur solution?

Collapse
 
larisho profile image
Gab

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)

Some comments may only be visible to logged-in visitors. Sign in to view all comments.