Problem

Given a vector vec of n natural numbers (each number is in the range [1..n]), we need to return "missing" natural numbers that do not appear in vec.

This puzzle is similar to Find the missing natural number in a vector puzzle where we had to find just 1 missing number (looking ahead, that would lead to a completely different implementation).

Examples:

Solution

fn find_missing_numbers_in_vector(vec: &mut Vec<i32>) -> Vec<i32> {
    for i in 0..vec.len() {
        let num = vec[i];
        let corr_index = (num.abs() - 1) as usize;
        vec[corr_index] = -1 * vec[corr_index].abs();
    }

    vec.iter()
        .enumerate()
        .filter_map(|(i, &num)| if num > 0 { Some((i + 1) as i32) } else { None })
        .collect()
}

Explanation

We can solve the puzzle without using extra space using the negation trick. We know that the input vector vec could contain only numbers in the range [1..n] (where n is the length of the input vector). It means that we can iterate over the vector and for each element num = vec[i] find a corresponding index corr_index = num.abs() - 1 and negate the number at that index. By doing so, we effectively mark an element as present by negating another element at the corresponding index.

After this exercise, all positive numbers (not marked by the negation) would represent the missing numbers: for a positive number num at the index i, the corresponding "missing" number would be equal to i + 1.

Complexity

The time complexity of this solution is O(n) (where n is the size of the input vector). The axiliary space complexity is O(1).

---

Rust Playground with this code