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

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

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: