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.
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; }}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.