LeetCode 448: Find All Numbers Disappeared in an Array

Problem Restatement

We are given an array nums of length n.

Every value in the array is in the range:

1 <= nums[i] <= n

We need to return all numbers from 1 to n that do not appear in nums.

The official problem asks for all integers in [1, n] that are missing from the array. The constraints are n == nums.length, 1 <= n <= 10^5, and 1 <= nums[i] <= n.

Input and Output

Item	Meaning
Input	Integer array nums
Output	List of missing numbers
Value range	1 to n
Array length	n
Goal	Find values in [1, n] absent from nums

Example function shape:

def findDisappearedNumbers(nums: list[int]) -> list[int]:
    ...

Examples

Example 1:

nums = [4, 3, 2, 7, 8, 2, 3, 1]

The range is:

[1, 2, 3, 4, 5, 6, 7, 8]

The numbers present in nums are:

1, 2, 3, 4, 7, 8

The missing numbers are:

[5, 6]

Example 2:

nums = [1, 1]

The range is:

[1, 2]

Only 1 appears.

So the answer is:

[2]

First Thought: Use a Set

The simplest solution is to store all numbers in a set:

seen = set(nums)

Then scan from 1 to n and collect values that do not appear in seen.

This is correct and easy.

But it uses O(n) extra space.

We can solve it with constant extra space by using the input array itself as a marker.

Key Insight

Because every number is between 1 and n, every number can point to an index.

For a value x, its index is:

x - 1

So when we see value x, we mark index x - 1 as visited.

A common in-place mark is to make the value at that index negative.

For example:

nums = [4, 3, 2, 7, 8, 2, 3, 1]

When we see 4, we mark index 3.

When we see 3, we mark index 2.

When we see 2, we mark index 1.

After marking all seen values, any index that still has a positive value corresponds to a missing number.

If index i is still positive, then number:

i + 1

never appeared.

Algorithm

First pass:

For each number num in nums:

1. Compute:

index = abs(num) - 1

2. Mark the corresponding index as seen:

nums[index] = -abs(nums[index])

We use abs(num) because num may already have been made negative by an earlier mark.

Second pass:

For every index i:

If:

nums[i] > 0

then i + 1 is missing.

Append it to the answer.

Return the answer.

Correctness

Each value x in the array maps to exactly one index, x - 1.

During the first pass, whenever the algorithm sees x, it marks nums[x - 1] as negative. Therefore, after the first pass, nums[x - 1] is negative for every value x that appeared in the input.

Now consider a number y from 1 to n.

If y appeared in nums, then the first pass marked index y - 1, so nums[y - 1] is negative.

If y did not appear in nums, then no step ever marked index y - 1, so nums[y - 1] remains positive.

The second pass returns exactly those indices whose values remain positive, converted back to numbers by adding 1.

Therefore, the returned list contains exactly all missing numbers.

Complexity

Metric	Value	Why
Time	O(n)	Two linear passes over the array
Space	O(1)	The input array is reused for marking

The output list is not counted as extra working space.

Implementation

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

        missing = []

        for i, value in enumerate(nums):
            if value > 0:
                missing.append(i + 1)

        return missing

Code Explanation

The first loop marks every value that appears:

for num in nums:

The mapped index is:

index = abs(num) - 1

The abs call is necessary because previous iterations may already have made some numbers negative.

We mark the value as seen:

nums[index] = -abs(nums[index])

Using -abs(...) keeps the number negative even if it was already marked.

Then we scan the array again:

for i, value in enumerate(nums):

Any positive value means its index was never marked:

if value > 0:
    missing.append(i + 1)

The missing number is i + 1, because value 1 maps to index 0, value 2 maps to index 1, and so on.

Testing

def run_tests():
    s = Solution()

    assert s.findDisappearedNumbers(
        [4, 3, 2, 7, 8, 2, 3, 1]
    ) == [5, 6]

    assert s.findDisappearedNumbers(
        [1, 1]
    ) == [2]

    assert s.findDisappearedNumbers(
        [1]
    ) == []

    assert s.findDisappearedNumbers(
        [2, 2]
    ) == [1]

    assert s.findDisappearedNumbers(
        [1, 2, 3, 4, 5]
    ) == []

    assert s.findDisappearedNumbers(
        [5, 4, 3, 2, 1]
    ) == []

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Standard example	Checks multiple missing numbers
[1, 1]	Checks duplicate causing one missing number
Single element	Checks smallest array
[2, 2]	Checks missing first value
Already complete range	Checks no missing values
Reversed complete range	Checks order does not matter