Find All Numbers Disappeared in an Array
Last Updated: March 29, 2026
Understanding the Problem
We have an array of n integers, and every value falls in the range [1, n]. Some numbers in that range appear once, some appear more than once (as duplicates), and some don't appear at all. Our job is to find the ones that are missing.
The constraint that values are in [1, n] is the crucial detail. It means there's a natural one-to-one mapping between array indices (0 to n-1) and the values we expect (1 to n). If every number appeared exactly once, we'd have a permutation of [1, n]. The duplicates are the reason some numbers go missing. So the real question is: how can we efficiently figure out which numbers from [1, n] never show up?
Key Constraints:
1 <= n <= 10^5→ With n up to 100,000, O(n^2) would mean 10 billion operations, which is too slow. We need O(n) or O(n log n) at most.1 <= nums[i] <= n→ Every value maps naturally to an index in the array (value - 1). This is a strong hint that we can use the array itself as a tracking structure.- Follow-up asks for O(n) time and O(1) extra space → This rules out using a hash set or boolean array. We need to mark visited numbers using the input array itself.
Approach 1: Hash Set
Intuition
The most natural approach: throw all the numbers into a set, then check which numbers from 1 to n are missing. A set gives us O(1) lookups, so the whole process is straightforward.
This doesn't satisfy the follow-up's space requirement, but it's the clearest way to think about the problem and a good starting point in an interview.
Algorithm
- Insert all elements of
numsinto a hash set. - Iterate through numbers from 1 to n.
- For each number, check if it exists in the set.
- If it doesn't, add it to the result list.
- Return the result list.
Example Walkthrough
Input:
Build the set: {1, 2, 3, 4, 7, 8}. Then check each number from 1 to 8:
Code
- Time Complexity: O(n). Building the set takes O(n). Iterating from 1 to n and checking membership is O(n) with O(1) per lookup.
- Space Complexity: O(n). The hash set stores up to n elements.
This approach works correctly but uses O(n) extra space. Since values are in [1, n], each value points to a valid index. What if we used the input array itself as our bookkeeping structure?
Approach 2: Negation Marking (Optimal)
Intuition
Since every value in the array is between 1 and n, each value naturally maps to an index: the value v maps to index v - 1. If we could "mark" each index that gets pointed to, then any unmarked index tells us its corresponding number is missing.
But how do you mark an index without extra space? By negating the value at that position. All values start positive (they're in [1, n]), so a negative value at index i means the number i + 1 exists somewhere in the array. After one pass of marking, a second pass finds all indices still holding positive values. Those are our missing numbers.
The negation trick works because of two properties. First, all values are positive to begin with, so "negative" is an unambiguous marker meaning "this index's number has been seen." Second, the mapping from value to index (value - 1) stays valid even after negation, because we always take the absolute value before computing the index.
Each number "claims" its corresponding index by flipping the sign. If two copies of the same number both try to claim the same index, the second one finds it already negative and moves on. At the end, any index that was never claimed still holds a positive value, and the number that would have claimed it (index + 1) is the missing one.
Algorithm
- First pass (marking): For each element, compute the index it maps to:
index = |nums[i]| - 1. Ifnums[index]is positive, negate it to mark thatindex + 1is present. - Second pass (collecting): Iterate through the array. For each index
iwherenums[i]is still positive, the numberi + 1is missing. Add it to the result. - Return the result list.
Example Walkthrough
Code
- Time Complexity: O(n). Two passes through the array, each O(n).
- Space Complexity: O(1) extra space. We only use a few variables. The result list doesn't count as extra space per the problem's follow-up constraint.
The negation approach modifies the input array. What if instead of marking, we physically sorted each number into its home position?
Approach 3: Cyclic Sort
Intuition
Since every value is in [1, n], each number has a "home" position: the number v belongs at index v - 1. If we could place every number in its home, then a simple scan would reveal which positions are occupied by the wrong number, and those wrong positions correspond to missing numbers.
This is the cyclic sort pattern. Instead of marking, we physically move each number to where it belongs. After sorting, index i should hold the value i + 1. Any index where this isn't true tells us i + 1 is missing.
Cyclic sort exploits the same value-to-index mapping as the negation approach, but instead of marking, it physically places each number at its home. The while loop at each position keeps swapping until either the current number reaches its home or the home already has the correct value (meaning it's a duplicate with nowhere to go).
Despite the nested while loop inside a for loop, each element is swapped at most once to its final position. Once a number lands in its home, it never moves again. So the total number of swaps across all iterations is at most n, giving O(n) total time.
Algorithm
- Iterate through the array. For each position
i, repeatedly swapnums[i]into its correct position (nums[i] - 1) until the current element is already in the right place or the target position already holds the correct value (duplicate). - After the cyclic sort, iterate through the array again. For each index
i, ifnums[i] != i + 1, theni + 1is a missing number. - Return the result list.
Example Walkthrough
Code
- Time Complexity: O(n). Each element is swapped at most once to its correct position. The total swaps across the entire array is bounded by n.
- Space Complexity: O(1) extra space. Only a few variables for swapping. The result list doesn't count as extra space per the problem statement.