Watch 10 video solutions for Find All Numbers Disappeared in an Array, a easy level problem involving Array, Hash Table. This walkthrough by NeetCode has 61,800 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: nums = [4,3,2,7,8,2,3,1] Output: [5,6]
Example 2:
Input: nums = [1,1] Output: [2]
Constraints:
n == nums.length1 <= n <= 1051 <= nums[i] <= n
Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Problem Overview: You are given an array of size n where values are in the range 1..n. Some numbers appear twice while others are missing. The task is to return all numbers from 1 to n that do not appear in the array.
Approach 1: Index Marking (O(n) time, O(1) extra space)
This approach uses the array itself as a presence marker. Since every value is between 1 and n, you can treat each value as an index reference. Iterate through the array, compute index = abs(nums[i]) - 1, and mark that position as visited by making the value negative. After this pass, any index that still contains a positive number means the corresponding value (index + 1) never appeared in the array.
The key insight is that the value range matches the index range, allowing you to encode presence directly inside the array. This avoids extra memory and keeps the runtime linear. A second iteration collects indices with positive values to build the result list. This technique is common in array problems where values map directly to positions.
Approach 2: Set-Based Method (O(n) time, O(n) space)
This method uses a hash table (or set) to track which numbers exist in the array. First iterate through the array and insert each element into a set. Then iterate from 1 to n and check whether each number exists in the set. If a number is missing from the set, add it to the result.
The implementation is straightforward and easy to reason about. Hash lookups run in average O(1) time, so the total runtime remains linear. The tradeoff is extra memory proportional to n. This version is useful when modifying the input array is not allowed or when clarity is preferred over space optimization.
Recommended for interviews: Interviewers usually expect the Index Marking technique because it demonstrates strong understanding of array constraints and in-place optimization. The set-based solution shows the basic idea quickly, but the in-place approach proves you can reduce auxiliary space while maintaining O(n) time complexity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Index Marking | O(n) | O(1) | Best for interviews and memory‑efficient solutions where modifying the array is allowed |
| Set-Based Method | O(n) | O(n) | When input modification is not allowed or when prioritizing clarity over space optimization |