448. Find All Numbers Disappeared in An Array - Explanation

Problem Link

Description

You are given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Note: You can return the integers in any 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[i] <= nums.length <= 100,000

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Hash Set

Intuition

We need to find numbers in the range [1, n] that are missing from the array. A simple approach is to create a set containing all numbers from 1 to n, then remove each number we find in the array. Whatever remains in the set are the missing numbers.

Algorithm

1. Create a set containing all integers from 1 to n.
2. For each number in the input array, remove it from the set.
3. Return the remaining elements in the set as a list.

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        store = set(range(1, n + 1))

        for num in nums:
            store.discard(num)

        return list(store)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

2. Boolean Array

Intuition

Instead of using a set, we can use a boolean array where mark[i] indicates whether the number i+1 is present in the input. We first mark all numbers that appear, then collect all indices where the mark is still false.

Algorithm

1. Create a boolean array mark of size n, initialized to false.
2. For each number in the input array, set mark[num - 1] = true.
3. Iterate through indices 1 to n:
   • If mark[i - 1] is false, add i to the result.
4. Return the result list.

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        mark = [False] * n

        for num in nums:
            mark[num - 1] = True

        res = []
        for i in range(1, n + 1):
            if not mark[i - 1]:
                res.append(i)
        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

3. Sorting

Intuition

After sorting, we can use a two-pointer technique to find missing numbers. We iterate through numbers 1 to n and use a pointer to track our position in the sorted array. If the current number is not found at the pointer position, it must be missing.

Algorithm

1. Sort the array.
2. Initialize a pointer idx = 0.
3. For each number from 1 to n:
   • Move idx forward while nums[idx] < num (skip duplicates and smaller values).
   • If idx reaches the end or nums[idx] > num, the number is missing; add it to the result.
4. Return the result list.

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        nums.sort()

        res = []
        idx = 0
        for num in range(1, n + 1):
            while idx < n and nums[idx] < num:
                idx += 1
            if idx == n or nums[idx] > num:
                res.append(num)
        return res

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

---

4. Negative Marking

Intuition

Since values are in range [1, n], we can use the input array itself as a marker. For each value v, we mark the position v-1 as visited by making it negative. After processing all values, any position that remains positive corresponds to a missing number.

Algorithm

1. For each number in the array:
   • Compute the index as abs(num) - 1.
   • Make nums[idx] negative (use absolute value to handle already-negated elements).
2. Iterate through the array:
   • If nums[i] > 0, the number i + 1 is missing; add it to the result.
3. Return the result list.

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

        res = []
        for i, num in enumerate(nums):
            if num > 0:
                res.append(i + 1)
        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ since we modified the input array without using extra space.

---

Common Pitfalls

Confusing Indices and Values

Since values are in the range [1, n] but indices are [0, n-1], it is easy to mix them up. When marking position i as visited, remember that value v maps to index v-1. Similarly, when checking which numbers are missing, index i corresponds to the number i+1.

Double-Negating Already Marked Values

When using negative marking, if you negate a value that is already negative, it becomes positive again and appears as if that position was never visited. Always use abs() before negating to ensure the value becomes negative regardless of its current sign.