# Rust Interview Puzzles: Move all zeros present in a vector to the end

·

### Problem

In a provided vector vec we need to move all 0 elements to the end of the vector. A relative order of other elements should not change.

#### Example 1:

Input: vec = [5, 0, 0, 2, 3, 0, 4, 0, 1]
Output: [5, 2, 3, 4, 1, 0, 0, 0, 0]

#### Example 2:

Input: vec = [0, 0, 8, 6, 0, 0]
Output: [8, 6, 0, 0, 0, 0]

#### Example 3:

Input: vec = [1, 2, 3]
Output: [1, 2, 3]

### Solution

fn move_zeros_to_end(vec: &mut Vec<i32>) -> &Vec<i32> {
let mut zero_count = 0;

(0..vec.len()).for_each(|index| {
if vec[index] == 0 {
zero_count += 1;
} else if zero_count > 0 {
vec[index - zero_count] = vec[index];
vec[index] = 0;
}
});

return vec;
}

### Explanation

We can solve the puzzle in a single pass over the provided vector vec. As we go through the vector vec, we maintain zero_count of 0 elements we come across. At the same time, we shift non-zero elements to the left to index - zero_count position, and fill their place with 0.

### Complexity

The time complexity of this solution is O(n) (n is a size of the input vector).

Rust Playground with this code