Arrays & Hashing · 166Easy
Find All Numbers Disappeared in an Array
Given an array nums of n integers where each nums[i] is in the range [1, n], return an array of all the integers in [1, n] that do not appear in nums. Any order is accepted.
Constraints
- n == nums.length, 1 <= n <= 10^5
- 1 <= nums[i] <= n
Examples
findDisappearedNumbers([4, 3, 2, 7, 8, 2, 3, 1]) -> [5, 6] // any order findDisappearedNumbers([1, 1]) -> [2] findDisappearedNumbers([1]) -> [] // n = 1, nothing missing findDisappearedNumbers([2, 2]) -> [1] findDisappearedNumbers([1, 2, 3]) -> [] // a permutation of 1..n findDisappearedNumbers([3, 3, 3, 3]) -> [1, 2, 4] // all the same value; any order
Edge cases
- Nothing missing (a permutation of 1..n) returns [].
- Every slot holds the same value, so n - 1 numbers are missing.
- FOLLOW-UP
- Could you do it without extra space (the returned list does not count) in O(n) time?
Show the target complexity (spoiler)
- Naive
- O(n) time, O(n) space — put every value in a Set, then check 1..n.
- Target
- O(n) time, O(1) extra space — for each value v, negate nums[|v| - 1]; indices that stay positive are the missing numbers.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/01-arrays-hashing/166-find-all-numbers-disappeared-in-an-array.js ./practice c 166