AlgoInsight

DSA problem

Find All Numbers Disappeared in an Array

EasyHash TablesPattern: Index as Hash Keytop600AmazonGoogleMicrosoftApple

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

A straightforward solution uses a hash set of seen values, but the elegant optimal solution treats the array itself as a hash table. Because every value is in the range [1, n], each value v corresponds to index v - 1. By negating the number at the index encoded by each value, the array marks which numbers are present. Indices that remain positive after this pass correspond to the missing numbers.

Follow up: Could you solve it without extra space and in O(n) runtime? (The output array does not count as extra space.)

Examples

Example 1
Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
Explanation: The array has 8 elements, so the full range is 1 to 8. The values 5 and 6 never appear, so they are returned.
Example 2
Input: nums = [1,1]
Output: [2]
Explanation: The range is 1 to 2. The value 1 appears but 2 is missing, so the answer is [2].
Example 3
Input: nums = [2,2]
Output: [1]
Explanation: The range is 1 to 2. The value 2 appears but 1 is missing, so the answer is [1].

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

hash-tablearrayin-place

Browse all DSA problems