Find All Numbers Disappeared in an Array

Problem

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 <= 105
• 1 <= nums[i] <= n

Solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    const map = Array(nums.length).fill(false);
    for (const n of nums) {
        map[n - 1] = true;
    }

    const res = map.reduce((acc, cur, i) => {
        if (!cur) {
            acc.push(i + 1);
        }
        return acc;
    }, []);

    return res;
};

Use a hashmap map to keep track of which values in the range [1, n] appeared before with true, and return the indices plus one of the entries that is false.

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.

Solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    for (const n of nums) {
        const val = Math.abs(n);
        if (nums[val - 1] > 0) {
            nums[val - 1] *= -1;
        }
    }

    const res = nums.reduce((acc, cur, i) => {
        if (cur > 0) {
            acc.push(i + 1);
        }
        return acc;
    }, []);

    return res;
};

To use no extra space, we use the provided array nums as the hashmap. More specifically, we iterate through nums and set nums[i] to be negative if i + 1 appears in nums (ie. nums[i] is positive if i + 1 never appears in nums). Thus, we can iterate through nums one more time and construct our output array res to contain i + 1 if nums[i] > 0.