Problem Statement:
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.length
- 1 <= n <= 105
- 1 <= nums[i] <= n
Solution:
Algorithm:
- Create a HashSet
- Create a List
- Add all the elements of the array to the HashSet
- Iterate from 1 to the length of the array
- If the HashSet does not contain the number, add it to the List
- Return the List
Code:
public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
HashSet<Integer> hs = new HashSet<>();
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
hs.add(nums[i]);
}
for (int i = 1; i <= nums.length; i++) {
if (!hs.contains(i)) {
result.add(i);
}
}
}
}
Time Complexity:
O(n)
Space Complexity:
O(n)
Top comments (0)