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.
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:
nums.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.
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.
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:
nums.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.
Time Complexity: O(n)
Space Complexity: O(n), due to use of additional boolean array to track presence of numbers.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
Find All Numbers Disappeared in an Array - Leetcode 448 - Python • NeetCode • 61,800 views views
Watch 9 more video solutions →Practice Find All Numbers Disappeared in an Array with our built-in code editor and test cases.
Practice on FleetCode