Find All Numbers Disappeared in an Array
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward approach. We iterate through all the numbers from 1 to n. For each number, we perform another iteration through the input array nums to check if the number exists. If it doesn't, we add it to our list of disappeared numbers.
Algorithm
-
- Initialize an empty list
resultto store the disappeared numbers.
- Initialize an empty list
-
- Get the size of the array,
n.
- Get the size of the array,
-
- Loop through each integer
ifrom 1 ton.
- Loop through each integer
-
- For each
i, search for its presence in thenumsarray by iterating throughnums.
- For each
-
- If
iis not found innumsafter checking all its elements, addito theresultlist.
- If
-
- After the outer loop finishes, return the
resultlist.
- After the outer loop finishes, return the
Walkthrough
The algorithm works by checking every number in the range [1, n] for its presence in the input array nums.
- We loop from
i = 1ton. - In each iteration, we have a flag, say
found, initialized tofalse. - We then start a nested loop to traverse the
numsarray. - If we find an element in
numsthat is equal toi, we setfoundtotrueand break the inner loop, as we only need to know if it exists at least once. - After the inner loop completes, if the
foundflag is stillfalse, it meansiwas not present innums, so we add it to our result list. - This process is repeated for all numbers from 1 to
n.
import java.util.ArrayList;import java.util.List; class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { List<Integer> result = new ArrayList<>(); int n = nums.length; for (int i = 1; i <= n; i++) { boolean found = false; for (int num : nums) { if (num == i) { found = true; break; } } if (!found) { result.add(i); } } return result; }}Complexity
Time
O(n^2), where `n` is the number of elements in the array. For each of the `n` numbers from 1 to `n`, we might scan the entire array of `n` elements.
Space
O(1) extra space. The space used by the result list is not considered extra space as per the problem description.
Trade-offs
Pros
Simple to understand and implement.
Does not modify the input array.
Uses constant extra space (excluding the result list).
Cons
Very inefficient, with a quadratic time complexity.
Will result in a 'Time Limit Exceeded' error on most platforms for larger inputs.
A more optimized approach involves using a data structure that provides fast lookups, such as a hash set. We can first iterate through the input array and store all its elements in a hash set. Then, we iterate from 1 to n, and for each number, we check if it's in the hash set. If it's not, we add it to the result list.
Algorithm
-
- Create a
HashSetnamedseen.
- Create a
-
- Iterate through each number
numin the input arraynumsand add it to theseenset.
- Iterate through each number
-
- Initialize an empty list
result.
- Initialize an empty list
-
- Get the size of the array,
n.
- Get the size of the array,
-
- Loop through each integer
ifrom 1 ton.
- Loop through each integer
-
- Check if
iis present in theseenset. This is an O(1) average time operation.
- Check if
-
- If
iis not in the set, add it to theresultlist.
- If
-
- Return the
resultlist.
- Return the
Walkthrough
This method improves the time complexity by sacrificing space. The core idea is to trade space for time by using a hash set to record which numbers are present in the input array.
- First, create a
HashSetand populate it with all the numbers from thenumsarray. This takes O(n) time. - Then, create an empty list for the results.
- Loop from
i = 1ton. For eachi, check if it exists in the hash set. Checking for an element in a hash set takes, on average, O(1) time. - If
iis not in the set, it means it's a disappeared number, so add it to the result list. - This second loop also takes O(n) time.
- The total time complexity is therefore linear.
import java.util.ArrayList;import java.util.HashSet;import java.util.List;import java.util.Set; class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int num : nums) { seen.add(num); } List<Integer> result = new ArrayList<>(); int n = nums.length; for (int i = 1; i <= n; i++) { if (!seen.contains(i)) { result.add(i); } } return result; }}Complexity
Time
O(n). It takes O(n) to build the hash set and another O(n) to iterate from 1 to `n`.
Space
O(n). In the worst case, all numbers in `nums` are unique, and the hash set will store `n` elements.
Trade-offs
Pros
Much faster than the brute-force approach, with a linear time complexity.
Relatively easy to understand.
Does not modify the input array.
Cons
Requires extra space proportional to the number of elements in the array, which does not meet the follow-up constraint of O(1) space.
This is the most optimal approach, satisfying the follow-up constraint of O(1) extra space. The key insight is that the numbers are in the range [1, n], which corresponds to the valid indices [0, n-1] of the array. We can use the array itself to mark the presence of numbers. We iterate through the array, and for each number x, we go to the index x-1 and mark it (e.g., by negating the value at that index). A second pass over the array allows us to find which indices were not marked, corresponding to the missing numbers.
Algorithm
-
- Iterate through the
numsarray. For each elementnum:
- Iterate through the
-
- Calculate the target index:
index = Math.abs(num) - 1.
- Calculate the target index:
-
- If the value at
nums[index]is positive, multiply it by -1 to mark it as seen.
- If the value at
-
- After the first loop, initialize an empty list
result.
- After the first loop, initialize an empty list
-
- Iterate through the
numsarray fromi = 0ton-1.
- Iterate through the
-
- If
nums[i]is positive, it means the numberi + 1was never in the original array. Addi + 1toresult.
- If
-
- Return the
resultlist.
- Return the
Walkthrough
This clever approach utilizes the input array itself as a hash map to keep track of the numbers we've seen, thus achieving O(1) space complexity.
- The values in the array range from
1ton. This means we can map each valuexto an indexx - 1. - We iterate through the
numsarray once. For each numbernums[i], we find the corresponding indexindex = Math.abs(nums[i]) - 1. We use the absolute value because the element atnums[i]might have been negated in a previous step. - At this
index, we mark the elementnums[index]as seen by making it negative. If it's already negative, we leave it as is. This ensures that even if a number appears multiple times, its corresponding index is marked only once. - After this first pass, the array is modified. For any number
kfrom1tonthat was present in the original array, the element at indexk-1will now be negative. - We then perform a second pass through the modified array from index
i = 0ton-1. - If we find that
nums[i]is positive, it means the numberi + 1was never seen in the original input. We addi + 1to our result list. - Finally, we return the result list.
import java.util.ArrayList;import java.util.List; class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { // First pass: Mark seen numbers by negating the value at the corresponding index. for (int i = 0; i < nums.length; i++) { int index = Math.abs(nums[i]) - 1; if (nums[index] > 0) { nums[index] = -nums[index]; } } List<Integer> result = new ArrayList<>(); // Second pass: Find the positive numbers, which correspond to missing integers. for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { result.add(i + 1); } } return result; }}Complexity
Time
O(n). We perform two separate passes through the array, each taking O(n) time. O(n) + O(n) = O(n).
Space
O(1) extra space. The modification is done in-place, and the space for the result list is excluded.
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal space complexity of O(1) (as the result list is not counted).
Meets the follow-up constraints.
Cons
Modifies the input array. If the caller needs the original array to be preserved, a copy must be made first, which would use O(n) space.
Solutions
Solution
class Solution {public List<Integer> findDisappearedNumbers(int[] nums) { int n = nums.length; for (int x : nums) { int i = Math.abs(x) - 1; if (nums[i] > 0) { nums[i] *= -1; } } List<Integer> ans = new ArrayList<>(); for (int i = 0; i < n; i++) { if (nums[i] > 0) { ans.add(i + 1); } } return ans; }}class Solution {public: vector<int> findDisappearedNumbers(vector<int> &nums) { int n = nums.size(); for (int &x : nums) { int i = abs(x) - 1; if (nums[i] > 0) { nums[i] = -nums[i]; } } vector<int> ans; for (int i = 0; i < n; ++i) { if (nums[i] > 0) { ans.push_back(i + 1); } } return ans; }};class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: for x in nums: i = abs(x) - 1 if nums[i] > 0: nums[i] *= - 1 return [i + 1 for i in range(len(nums)) if nums[i] > 0]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.