Find All Numbers Disappeared in an Array - Solution & Explanation
Problem Statement
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.
Approach Overview
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 1: Approach 1: Index Marking
This approach uses the properties of the array and its indices to track missing numbers. By iterating through the array and using the values to mark the corresponding indices, we can identify which indices were never marked and thus determine the missing numbers.
Steps:
- Iterate over each element in the array
nums. - For each element, compute its corresponding index by subtracting 1 (as the array is zero-based).
- Use this index to mark the original array as visited by negating the value at that index.
- After processing all numbers, iterate over the array once more. The indices with positive values indicate the missing numbers, which are the result.
This C solution implements index marking by negating the values at positions corresponding to the numbers seen in the array. It iterates over the array twice: first to mark visited numbers and second to collect those which are still positive, indicating those numbers are missing.
Complexity
Time Complexity: O(n) - where n is the number of elements in the array because we are iterating over the array twice.
Space Complexity: O(1) - as no additional data structure is used apart from the output list and input array is modified in-place.
Approach 2: Approach 2: Set-Based Method
In this approach, we utilize a set to only store unique numbers from 1 to n that appear in the input array. By comparing this set to the complete range of numbers, we can directly determine those not present in the input.
Steps:
- Initialize a set containing all the numbers in
nums. - Create a result list which will store numbers not present in the set, iterating from 1 to n.
- For each number in the iteration, check if it is missing in the set and append to the result list if so.
In this solution, a boolean array acts as a set storing flags for numbers detected in the input. Subsequent traversal is made to seek indices flagged false, representing the missing numbers.
Complexity
Time Complexity: O(n)
Space Complexity: O(n), due to use of additional boolean array to track presence of numbers.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Index Marking | Time Complexity: O(n) - where n is the number of elements in the array because we are iterating over the array twice. |
| Approach 2: Set-Based Method | Time Complexity: O(n) |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Find All Numbers Disappeared in an Array - Leetcode 448 - Python • NeetCode • 63,701 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find All Numbers Disappeared in an Array easy or hard?
Find All Numbers Disappeared in an Array Python/Java solution
How to solve Find All Numbers Disappeared in an Array in O(n)?
What is the best approach for Find All Numbers Disappeared in an Array?
Is Find All Numbers Disappeared in an Array asked at Google/Amazon/Meta?
What data structure is used in Find All Numbers Disappeared in an Array?
What is the time complexity of Find All Numbers Disappeared in an Array?
Ready to solve this problem?
Practice Find All Numbers Disappeared in an Array with our built-in code editor and test cases.
Practice on FleetCode