Find All Numbers Disappeared in an Array
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] drives every approach here. It creates a 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, the array would be a permutation of [1, n]. Duplicates are why some numbers go missing: each duplicate takes a slot that some other number would have occupied. The problem reduces to finding which numbers from [1, n] never appear.
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 to a valid index in the array (value - 1), which lets the array double as its own tracking structure with no extra memory.- 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
Put every number into a hash set, then scan 1 to n and report whichever values the set does not contain. The set answers each membership query in O(1), so the whole thing runs in O(n).
This ignores the follow-up's space requirement, but it is the simplest correct solution and a useful baseline to optimize from.
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 from nums: {1, 2, 3, 4, 7, 8} (the duplicate 2 and 3 collapse to single entries). Then check each number from 1 to 8 against the set:
- 1 in set, 2 in set, 3 in set, 4 in set: skip all.
- 5 not in set: add 5 to result.
- 6 not in set: add 6 to result.
- 7 in set, 8 in set: skip both.
The result holds the two values the set never received:
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 works but uses O(n) extra space for the set. The next approach removes that cost by storing the "seen" information inside the input array itself, since every value already points to a valid index.
Approach 2: Negation Marking (Optimal)
Intuition
Every value in the array is between 1 and n, so the value v maps to index v - 1. Marking each index that some value points to leaves the unmarked indices corresponding to the missing numbers.
The mark itself goes inside the array, costing no extra space: negate the value at the target position. All values start positive (they are in [1, n]), so a negative value at index i records that the number i + 1 exists somewhere in the array. After one marking pass, a second pass collects every index still holding a positive value. Those positions are the missing numbers.
Two properties keep the marking unambiguous. Because every original value is positive, a sign of "negative" can only mean "some value pointed here," so it is a clean one-bit flag. And taking the absolute value before computing |nums[i]| - 1 recovers the original magnitude even after a position has already been negated, so the value-to-index mapping survives marking.
Duplicates do not corrupt the result. The first copy of a value negates its target index; a later copy finds that index already negative and the if (nums[index] > 0) guard skips it. So each present number flags its index at least once, and exactly the indices no value pointed to stay positive. Index i staying positive means no value equal to i + 1 exists, which is the definition of i + 1 being missing.
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 overwrites values with their negatives. The next approach also modifies the array but keeps the values intact, rearranging them into sorted positions instead of flipping signs.
Approach 3: Cyclic Sort
Intuition
Every value is in [1, n], so each number has a home position: the number v belongs at index v - 1. Once every number sits in its home, a single scan finds the positions holding the wrong number, and those positions correspond to the missing values.
This is the cyclic sort pattern. Each number is swapped to where it belongs in a series of in-place moves. After sorting, index i holds the value i + 1 whenever i + 1 is present. Any index where nums[i] != i + 1 means i + 1 never appeared.
The while loop swaps until either the current number reaches its home or that home already holds the correct value, which happens for duplicates that have nowhere left to go. The index nums[i] - 1 is always valid: values stay in [1, n] throughout, so the subscript stays in [0, n-1] and the swaps never go out of bounds.
Even though a while loop sits inside the for loop, the work is linear. Every swap moves at least one number into its final home, and once a number is home it never moves again. The array has n homes, so the total number of swaps over the whole run is at most n. Add the two linear scans and the algorithm is O(n).
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.