448. Find All Numbers Disappeared in an Array

Problem Statement

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:

Input: nums = [1,1]
Output: [2]

Constraints:

n == nums.length
1 <= n <= 10⁵
1 <= nums[i] <= n

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Click to open Hints

This is a really easy problem if you decide to use additional memory. For those trying to write an initial solution using additional memory, think counters!
However, the trick really is to not use any additional space than what is already available to use. Sometimes, multiple passes over the input array help find the solution. However, there's an interesting piece of information in this problem that makes it easy to re-use the input array itself for the solution.
The problem specifies that the numbers in the array will be in the range [1, n] where n is the number of elements in the array. Can we use this information and modify the array in-place somehow to find what we need?

Solution:

Rust

impl Solution {
    pub fn find_disappeared_numbers(nums: Vec<i32>) -> Vec<i32> {
        let mut res = Vec::new();
        let mut map = std::collections::HashMap::new();

        for i in 0..nums.len() {
            map.insert(nums[i], i);
        }

        for i in 1..=nums.len() {
            if !map.contains_key(&(i as i32)) {
                res.push(i as i32);
            }
        }

        res
    }
}

448. Find All Numbers Disappeared in an Array #

Problem Statement #

Solution: #

... #

448. Find All Numbers Disappeared in an Array

Problem Statement

Solution:

...