Find All Numbers Disappeared in an Array
(#448), Easy
Category: Array, Hash Table
Problem Statement
Given an array `nums` of `n` integers where `nums[i]` is in the range `[1, n]`, some elements appear **twice** and others appear **once**. Return *all the integers in the range* `[1, n]` *that do not appear in* `nums`.
Examples
Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output: [5, 6]
Explanation: The numbers 5 and 6 are missing from the range 1 to 8.
Input: nums = [1, 1]
Output: [2]
Explanation: Only number 2 is missing in the range 1 to 2.
Approach
Approach: Brute Force using Hash Map
- Initialize an empty `Map`.
- Loop through `nums` and add each number into the map.
- Create an empty array `ans`.
- Loop from 1 to n (inclusive):
- - If a number is not present in the map, push it to `ans`.
- Return the `ans` array.
// 🔹 Brute Force using Hash Map
var findDisappearedNumbers = function (nums) {
let map = new Map();
let ans = [];
for (let i = 0; i < nums.length; i++) {
map.set(nums[i], true);
}
for (let i = 1; i <= nums.length; i++) {
if (!map.has(i)) ans.push(i);
}
return ans;
};Approach: Optimized In-place Negative Marking
- Loop through each number in `nums`.
- For each value `val`, calculate `index = Math.abs(val) - 1`.
- Make `nums[index]` negative if it’s not already.
- Create a result array `result`.
- Loop through the array again:
- - If `nums[i]` is positive, then `i + 1` is missing → push to `result`.
- Return the `result` array.
// 🔹 Optimized In-place Negative Marking
var findDisappearedNumbers = function (nums) {
for (let i = 0; i < nums.length; i++) {
let index = Math.abs(nums[i]) - 1;
nums[index] = -Math.abs(nums[index]);
}
let result = [];
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) result.push(i + 1);
}
return result;
};Complexity
Time: O(n) – Both approaches scan the array twice
Space: O(n) for brute force, O(1) for optimized in-place version