Find All Numbers Disappeared in Array — Index Negation O(n) O(1) [Meta Easy]

Problem Statement

Input: [4,3,2,7,8,2,3,1] → [5,6] (5 and 6 are missing from [1..8]).

Intuition: For each number n, negate nums[|n|-1]. After the pass, any still-positive index i means i+1 was never seen.

C Solution
C++ Solution
Java Solution
JavaScript Solution
Python Solution
Complexity

C Solution

for(int i=0;i<n;i++){int idx=abs(nums[i])-1;if(nums[idx]>0)nums[idx]=-nums[idx];}

C++ Solution

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (int i = 0; i < (int)nums.size(); i++) {
            int idx = abs(nums[i]) - 1;
            if (nums[idx] > 0) nums[idx] = -nums[idx];
        }
        vector<int> res;
        for (int i = 0; i < (int)nums.size(); i++)
            if (nums[i] > 0) res.push_back(i + 1);
        return res;
    }
};

Java Solution

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];
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++)
            if (nums[i] > 0) res.add(i + 1);
        return res;
    }
}

JavaScript Solution

function findDisappearedNumbers(nums) {
    for (const n of nums) {
        const idx = Math.abs(n) - 1;
        if (nums[idx] > 0) nums[idx] = -nums[idx];
    }
    return nums.map((v,i) => v > 0 ? i+1 : 0).filter(Boolean);
}

Python Solution

def findDisappearedNumbers(nums):
    for n in nums:
        idx = abs(n) - 1
        if nums[idx] > 0: nums[idx] = -nums[idx]
    return [i+1 for i, v in enumerate(nums) if v > 0]

Complexity

| O(n) time | O(1) extra space |