448. Find All Numbers Disappeared in an Array
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 56.1%
Problem Breakdown
The problem requires us to identify all integers in the range [1, n] that do not appear in the given array nums. The input is an array of integers where each integer is within the range [1, n], and the length of the array is also n. The output should be a list of missing integers.
Inputs:
- An array
numsof integers where1 <= nums[i] <= n.
Outputs:
- A list of integers that are in the range
[1, n]but do not appear innums.
Implicit Constraints:
- The length of
numsis exactlyn. - Each integer in
numsis within the valid range[1, n]. - The returned list should not count as extra space for complexity calculations.
Tricky Edge Cases:
- An empty array (though the problem constraints prevent this).
- Arrays with all elements being the same.
- Arrays where all numbers from 1 to n are present.
Intuition
A brute-force approach would involve creating a set of all integers from 1 to n and then removing each integer found in nums. The remaining integers in the set would be the missing numbers. However, this approach requires extra space for the set and has a time complexity of O(n).
The key insight is to use the input array itself to track which numbers have been seen by marking their corresponding indices. This way, we can achieve the desired solution without using extra space.
Approach
- Iterate through the array: For each number
nums[i], treat it as an index (subtract 1 to adjust for zero-based indexing) and mark the value at that index as negative if it’s positive. - Identify missing numbers: After marking, any index with a positive value indicates that the corresponding number is missing from the array.
Algorithm:
- Iterate through each element in
nums.- For each element
nums[i], find the indexidx = abs(nums[i]) - 1. - If
nums[idx]is positive, mark it as negative by settingnums[idx] = -nums[idx].
- For each element
- After marking, iterate again to collect all indices with positive values. These indices correspond to missing numbers.
Complexity Analysis
Time Complexity: O(n)
- We make two passes through the array: one for marking and another for collecting results. Each pass is O(n).
Space Complexity: O(1) (excluding the output list)
- We modify the input array in place without using any additional data structures, thus achieving constant space complexity.
Solution
def findDisappearedNumbers(nums):
# Mark each number's corresponding index as negative
for num in nums:
idx = abs(num) - 1
if nums[idx] > 0:
nums[idx] = -nums[idx]
# Collect all indices with positive values, which are missing numbers
result = []
for i in range(len(nums)):
if nums[i] > 0:
result.append(i + 1)
return result
Edge Cases Handled
- All elements are the same: If all elements are the same, the marking step will only affect one index, and the rest will remain positive, correctly identifying missing numbers.
- No duplicates: The algorithm naturally handles arrays with no duplicates by marking indices accordingly.
- All numbers from 1 to n present: In this case, all indices will be marked negative, resulting in an empty output list as expected.