Find All Numbers Disappeared in an Array

Easy

Problem

An array of n integers has every value in 1..n, but some values repeat, so others are missing. Return every value in 1..n that does not appear, using O(1) extra space besides the output.

Example 1

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

Test cases

Case 1

Input:    [4,3,2,7,8,2,3,1]
Expected (any order): [5,6]

Case 2

Input:    [1,1]
Expected (any order): [2]

Case 3

Input:    [1,2,3]
Expected (any order): []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Mark by negating

Time O(n)Space O(1) extra

For each value v, negate nums[v − 1]. Indices still positive at the end were never visited.

function findDisappearedNumbers(nums) {
for (const x of nums) {
const i = Math.abs(x) - 1;
if (nums[i] > 0) nums[i] = -nums[i];
}
const res = [];
for (let i = 0; i < nums.length; i++) if (nums[i] > 0) res.push(i + 1);
return res;
}