Problem statement

Given an array nums of n integers where nums[i] is in the range [1, n], return all the numbers in [1, n] that do not appear in nums, in increasing order.

Example 1

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2

Input: nums = [1,1]
Output: [2]

Constraints

• 1 <= nums.length <= 30
• 1 <= nums[i] <= nums.length

Hints for Find All Numbers Disappeared in an Array

1. Hint 1

   Mark which values 1..n you have seen, then collect the unseen ones.

2. Hint 2

   The classic O(1)-space trick negates nums[|x|-1] to mark presence.

How to solve Find All Numbers Disappeared in an Array

Values are confined to 1 .. n, which makes them usable as indices. Mark each value you see, then report the positions never marked — scanning upwards gives the increasing order the problem asks for.

Approach

1. Create a seen array of size n + 1, all false.
2. For each value x in the input, set seen[x] = true.
3. Scan v from 1 to n.
4. Collect every v whose flag is still false.

Why it works

Because the values and the index range coincide, membership becomes a constant-time array lookup rather than a search — which is what turns the naive O(n^2) scan into a linear one. Reporting in index order gives sorted output for free. The classic O(1)-space refinement encodes the same marks inside the input itself by negating nums[abs(x) - 1], then reads off the positions that stayed positive.

Complexity

• Time — O(n)
• Space — O(n), or O(1) using in-place sign marking

Pitfalls

• Values are 1-based while array indices are 0-based; size the seen array n + 1 or subtract one consistently.
• Duplicates are expected — marking the same slot twice must be harmless.
• Report the values 1 .. n, not the indices.
• With the in-place negation trick, always take the absolute value before indexing, since earlier marks may have flipped the sign.

Reference solution

Python

from typing import List

def findDisappeared(nums: List[int]) -> List[int]:
    present = set(nums)
    return [i for i in range(1, len(nums) + 1) if i not in present]

Java

public static int[] findDisappeared(int[] nums) {
    int n = nums.length;
    boolean[] seen = new boolean[n + 1];
    for (int x : nums) seen[x] = true;
    List<Integer> out = new ArrayList<>();
    for (int v = 1; v <= n; v++) {
        if (!seen[v]) out.add(v);
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < out.size(); i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> findDisappeared(vector<int>& nums) {
    int n = (int) nums.size();
    vector<bool> seen(n + 1, false);
    for (int x : nums) seen[x] = true;
    vector<int> out;
    for (int v = 1; v <= n; v++) {
        if (!seen[v]) out.push_back(v);
    }
    return out;
}

JavaScript

var findDisappeared = function(nums) {
    const present = new Set(nums);
    const out = [];
    for (let i = 1; i <= nums.length; i++) {
        if (!present.has(i)) out.push(i);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy