Back to solutions

Find All Numbers Disappeared in An Array

EasyArrays

List the numbers in [1, n] that are missing from the array.

Open problem
Constraints
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n

Mark by negating in place

Time O(n)Space O(1) extra

Because every value is in [1, n], use the array itself as a presence marker. For each value v, flip the sign of the slot at index v-1 to record that v was seen. Any slot still positive afterwards corresponds to a number that never appeared.

Key terms
in-place marking:
Encoding 'seen' information into the sign of existing array slots instead of a separate set.
index as value:
Mapping value v to position v-1, possible because values are bounded by n.
vector<int> findDisappearedNumbers(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int idx = abs(nums[i]) - 1;
        if (nums[idx] > 0) nums[idx] = -nums[idx];
    }
    vector<int> res;
    for (int i = 0; i < n; i++) if (nums[i] > 0) res.push_back(i + 1);
    return res;
}
Step by step
  1. For each element, take idx = abs(value) - 1.
  2. If nums[idx] is still positive, negate it to mark that idx+1 was seen.
  3. After the pass, scan once: every index i where nums[i] > 0 means i+1 never appeared.
  4. Collect those i+1 values in ascending order (natural from the scan).