Find All Numbers Disappeared in an Array
Easy · Arrays & Hashing · Array · Hash Table
Problem
You are given an array nums of n integers where every nums[i] lies in the range [1, n]. Some values may appear more than once, which means others do not appear at all.
Return all the integers in [1, n] that do not appear in nums, in any order.
A set of seen values solves it directly. Aim for O(n) time and O(1) extra space (the output list does not count).
Examples
Input: nums = [2,6,2,1,6,3] Output: [4,5]
Values 1, 2, 3 and 6 are present; 4 and 5 are not. The order of the answer does not matter.
Input: nums = [1,1,1] Output: [2,3]
Only 1 appears.
Input: nums = [2,1] Output: []
Every value in [1, 2] appears.
Constraints
- n == len(nums)
- 1 <= n <= 10^5
- 1 <= nums[i] <= n
Approaches
- Baseline: sort a copy, report the skipped values — time O(n log n), space O(n)
Follow-up
The same marks also tell you which values repeat (a slot already negative when you reach it). If the input must stay read-only and O(1) space is still required, there is no linear-time answer in general; sorting a copy (O(n) space) or counting with a set is the fallback.
Related problems
Start free on Cariara · Coding problems · System design studio
