LeetCode Problem 448 – Find All Numbers Disappeared in an Array
Problem Link: Link
Problem Statement
You are given an array nums of length n, where each element nums[i] lies in the range [1, n].
Your task is to return all numbers in the range [1, n] that do not appear in the array.
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 ≤ 10⁵1 ≤ nums[i] ≤ n
Approach
The goal is to identify numbers within the range 1 to n that are missing from the given array.
One straightforward way to solve this problem is by using a HashMap to track the presence of each number:
- Traverse the array and store each element in a HashMap.
- Iterate through the range
1ton. - For each number, check whether it exists in the HashMap.
- If a number is not present, add it to the result list.
This approach ensures that:
- Each element is processed only once.
- Lookup operations are efficient.
Time and Space Complexity
- Time Complexity:
O(n) - Space Complexity:
O(n)(due to the HashMap)
Solution Code (Java)
public List<Integer> findDisappearedNumbers(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
List<Integer> result = new ArrayList<>();
// Store all elements in the HashMap
for (int num : nums) {
map.put(num, 0);
}
// Check for missing numbers in the range [1, n]
for (int i = 1; i <= nums.length; i++) {
if (!map.containsKey(i)) {
result.add(i);
}
}
return result;
}
Final Notes
While this solution is simple and easy to understand, it uses additional space.
LeetCode also offers a constant space solution by modifying the input array in-place, which is worth exploring for optimization.
