Find All Numbers Disappeared in an Array
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): []
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;}