#448
Find All Numbers Disappeared in an Array
Easy Index marking
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
An array of n numbers has values in 1..n, some repeated. Return all values in 1..n that never appear, using no extra space besides the output.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: values are 1..n; which of them never appear?
Why this works: use the array as its own checklist. Seeing value v flips nums[v-1] negative. Positions that stay positive were never "visited".
Example: [4, 3, 2, 7, 8, 2, 3, 1]
after marking: [-4, -3, -2, -7, 8, 2, -3, -1]index 4 and 5 still positive → 5 and 6 are missing
✦Hints open one at a time
Every value v can point to an index: v - 1.
Mark "v was seen" by making nums[v - 1] negative.
↗Approach
For each value, negate the slot it points to (if not already negative). Afterwards, every index i that is still positive means i + 1 was never seen.
</>Solution (Java)
import java.util.*;
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int idx = Math.abs(nums[i]) - 1;
if (nums[idx] > 0) nums[idx] = -nums[idx]; // mark idx+1 as seen
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) ans.add(i + 1);
}
return ans;
}
}!Common mistake
Using nums[i] - 1 as the index after it was negated. Use Math.abs(nums[i]).
Complexity
- Time: O(n).
- Space: O(1) extra.
Topic: Arrays
