Problem Statement
This problem is from Leetcode – Find All Numbers Disappeared in an Array. 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]
Solution
The solution to this problem is simple enough. In first pass we’ll add all numbers from zero till the length of the array in a HashSet. In second pass we’ll check if any numbers are missing in this HashSet in comparison to the given array. See the code sample below:
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> intList = new ArrayList<Integer>();
Set<Integer> numSet = new HashSet<Integer>();
// add numbers in a Hashset
for(int i=0; i<nums.length; i++) {
numSet.add(nums[i]);
}
// now find the missing numbers
for(int i=1; i<=nums.length; i++) {
if(!numSet.contains(i)) {
System.out.println(i);
intList.add(i);
}
}
return intList;
} You can checkout the code from Github here: Find All Numbers Disappeared in an Array. See the performance of this approach below:
See the complexity below:
