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