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).