Find All Numbers Disappeared in an Array

How it works

Since values are in range [1, n], we can use the input array itself as a marker. For each value v, we mark the position v-1 as visited by making it negative. After processing all values, any position that remains positive corresponds to a missing number.

Steps

1. For each number in the array:
   • Compute the index as abs(num) - 1.
   • Make nums[idx] negative (use absolute value to handle already-negated elements).
2. Iterate through the array:
   • If nums[i] > 0, the number i + 1 is missing; add it to the result.
3. Return the result list.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) since we modified the input array without using extra space.

Things to watch for

Confusing Indices and Values

Since values are in the range [1, n] but indices are [0, n-1], it is easy to mix them up. When marking position i as visited, remember that value v maps to index v-1. Similarly, when checking which numbers are missing, index i corresponds to the number i+1.

Double-Negating Already Marked Values

When using negative marking, if you negate a value that is already negative, it becomes positive again and appears as if that position was never visited. Always use abs() before negating to ensure the value becomes negative regardless of its current sign.

from typing import List

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for num in nums:
            i = abs(num) - 1
            nums[i] = -1 * abs(nums[i])

        res = []
        for i, num in enumerate(nums):
            if num > 0:
                res.append(i + 1)
        return res

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (int num : nums) {
            int i = abs(num) - 1;
            nums[i] = -abs(nums[i]);
        }

        vector<int> res;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) {
                res.push_back(i + 1);
            }
        }
        return res;
    }
};