LeetCode 448 - Find All Numbers Disappeared in an Array

The problem asks us to find all the integers in the range [1, n] that are missing from an input array nums of length n.

leetcodeeasyarrayhash-table

LeetCode Problem 448

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

Problem Understanding

The problem asks us to find all the integers in the range [1, n] that are missing from an input array nums of length n. Each element in nums is guaranteed to be an integer between 1 and n inclusive, but some numbers in this range may not appear in the array, and some numbers may appear multiple times. The output is an array containing all integers from 1 to n that do not exist in nums.

For example, given nums = [4,3,2,7,8,2,3,1], the array has duplicates (2 and 3) and is missing 5 and 6. The correct output is [5,6].

The constraints indicate that n can be as large as 10^5, which means a naive quadratic solution will likely be too slow. Each element falls within the range [1, n], which is important because it allows us to use the input array itself for marking presence without extra space.

Important edge cases include arrays where all numbers are present (return empty), arrays where all numbers are missing except one, arrays of length 1, and arrays where duplicates cover the entire range except one number.

Approaches

The brute-force approach iterates over each number from 1 to n and checks if it exists in nums by scanning the array. This works correctly because it directly validates each possible number, but it is slow. For each of the n numbers, scanning an array of length n results in O(n²) time complexity, which is unacceptable for large inputs.

The optimal approach leverages the fact that the numbers in nums are all in the range [1, n]. This allows us to mark numbers as seen by modifying the input array itself. The key insight is to treat the array as a hash map: for each number num, we mark the element at index num - 1 as negative to indicate that num is present. After processing all numbers, the indices that remain positive correspond to the missing numbers. This approach uses O(1) extra space (ignoring the output array) and runs in O(n) time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Scan for each number from 1 to n in the array
Optimal O(n) O(1) Mark visited numbers in-place by negating the corresponding index

Algorithm Walkthrough

  1. Iterate through each number in the input array nums. For each number num, compute the corresponding index idx = abs(num) - 1. The abs is necessary because we may have already marked this index as negative in a previous iteration.
  2. Mark the number at index idx as negative to indicate that idx + 1 exists in the array. If it is already negative, leave it as is.
  3. After the first pass, iterate through the array again. For each index i where nums[i] is positive, it means that the number i + 1 did not appear in the original array.
  4. Collect all such numbers into a result array and return it.

Why it works: By marking indices corresponding to the numbers seen, we maintain a direct mapping between indices and numbers. The negative marking is a safe in-place modification because we never need the original sign of a number for future computations, only its absolute value. This guarantees that every missing number is detected by its positive index.

Python Solution

from typing import List

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        # Step 1: Mark indices corresponding to numbers present
        for num in nums:
            idx = abs(num) - 1
            if nums[idx] > 0:
                nums[idx] = -nums[idx]
        
        # Step 2: Collect indices that remain positive
        result = []
        for i, num in enumerate(nums):
            if num > 0:
                result.append(i + 1)
        
        return result

The Python implementation follows the algorithm exactly. The first loop marks all indices corresponding to numbers seen by negating them. The second loop scans for positive values, which indicate missing numbers. Using abs(num) ensures that previously marked negative numbers do not interfere with index computation.

Go Solution

func findDisappearedNumbers(nums []int) []int {
    n := len(nums)
    
    // Step 1: Mark indices corresponding to numbers present
    for _, num := range nums {
        idx := abs(num) - 1
        if nums[idx] > 0 {
            nums[idx] = -nums[idx]
        }
    }
    
    // Step 2: Collect indices that remain positive
    var result []int
    for i, num := range nums {
        if num > 0 {
            result = append(result, i+1)
        }
    }
    
    return result
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

In Go, the main difference is the need for an explicit abs function. The logic is otherwise identical: mark indices in place and collect positive values. Go slices handle dynamic appending naturally.

Worked Examples

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

Step-by-step processing:

Step nums state Action
Initial [4,3,2,7,8,2,3,1] -
Mark 4 [4,3,2,-7,8,2,3,1] nums[3] = -7
Mark 3 [4,3,-2,-7,8,2,3,1] nums[2] = -2
Mark 2 [4,-3,-2,-7,8,2,3,1] nums[1] = -3
Mark 7 [4,-3,-2,-7,8,2,-3,1] nums[6] = -3
Mark 8 [4,-3,-2,-7,8,2,-3,-1] nums[7] = -1
Mark 2 [4,-3,-2,-7,8,2,-3,-1] already negative
Mark 3 [4,-3,-2,-7,8,2,-3,-1] already negative
Mark 1 [-4,-3,-2,-7,8,2,-3,-1] nums[0] = -4

Second pass collects indices with positive values: indices 4 and 5 correspond to numbers 5 and 6. Output: [5,6].

Example 2: nums = [1,1]

After marking: [-1,1]. Index 1 is positive, meaning number 2 is missing. Output: [2].

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each loop over nums is O(n), no nested iterations
Space O(1) In-place marking, output array does not count as extra space

The algorithm is linear because it processes each element exactly twice, once for marking and once for collecting results. It does not use any additional data structures except the output array.

Test Cases

# provided examples
assert Solution().findDisappearedNumbers([4,3,2,7,8,2,3,1]) == [5,6]  # multiple missing numbers
assert Solution().findDisappearedNumbers([1,1]) == [2]  # only one missing number

# edge cases
assert Solution().findDisappearedNumbers([1]) == []  # single element present
assert Solution().findDisappearedNumbers([2]) == [1]  # single element missing
assert Solution().findDisappearedNumbers([1,2,3,4,5]) == []  # all numbers present
assert Solution().findDisappearedNumbers([2,2,2,2,2]) == [1,3,4,5]  # duplicates cover some numbers
assert Solution().findDisappearedNumbers([5,4,3,2,1]) == []  # all numbers present, unordered
assert Solution().findDisappearedNumbers([1,1,2,2]) == [3,4]  # multiple duplicates
Test Why
[4,3,2,7,8,2,3,1] Validates multiple missing numbers and duplicates
[1,1] Validates single missing number with duplicate
[1] Single element present, no missing numbers
[2] Single element missing, minimal size
[1,2,3,4,5] No missing numbers, all present
[2,2,2,2,2] Duplicates covering some numbers, multiple missing numbers
[5,4,3,2,1] All numbers present, unordered
[1,1,2,2] Multiple duplicates, checks correct identification of missing numbers

Edge Cases

One important edge case is an array of length 1. If the array contains