Find All Numbers Disappeared in an Array
Problem
Given an array nums with values in [1, n] (n = nums.length), return all integers in [1, n] that do not appear in nums. O(n) time, O(1) extra space.
nums = [4, 3, 2, 7, 8, 2, 3, 1][5, 6]def find_disappeared_numbers(nums):
for x in nums:
i = abs(x) - 1
if nums[i] > 0:
nums[i] = -nums[i]
return [i + 1 for i, v in enumerate(nums) if v > 0]function findDisappearedNumbers(nums) {
for (const x of nums) {
const i = Math.abs(x) - 1;
if (nums[i] > 0) nums[i] = -nums[i];
}
const res = [];
for (let i = 0; i < nums.length; i++) if (nums[i] > 0) res.push(i + 1);
return res;
}class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int x : nums) {
int i = Math.abs(x) - 1;
if (nums[i] > 0) nums[i] = -nums[i];
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) if (nums[i] > 0) res.add(i + 1);
return res;
}
}vector<int> findDisappearedNumbers(vector<int>& nums) {
for (int x : nums) {
int i = abs(x) - 1;
if (nums[i] > 0) nums[i] = -nums[i];
}
vector<int> res;
for (int i = 0; i < (int)nums.size(); i++) if (nums[i] > 0) res.push_back(i + 1);
return res;
}Explanation
Since every value lives in the range [1, n], each number has its own natural home slot in the array. We use the sign of a slot as a flag for "this number is present", which lets us find the missing ones without any extra space.
In phase 1 we walk through each value x and flip the slot at index abs(x) - 1 negative (only if it is still positive). We use abs because earlier flips may have already turned a slot negative. After this pass, every slot whose value appeared is negative.
In phase 2 we scan the array. Any slot that is still positive was never marked, which means the number i + 1 never showed up. We collect all those as the missing numbers.
Example: nums = [4, 3, 2, 7, 8, 2, 3, 1]. After marking, slots for present values 1,2,3,4,7,8 are negative. The slots at indices 4 and 5 stay positive, so the missing numbers are 5 and 6.
Two simple passes over the array, with no extra data structure, give the answer in linear time.