#448

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find All Numbers Disappeared in an Array

Identify all missing numbers in an array using efficient scanning and hash-based lookup for optimal performance.

Problem Statement

Given an array nums of n integers where each element is in the range [1, n], identify and return all numbers in this range that are not present in nums. Your solution should consider array scanning and hash lookup patterns to efficiently find missing values.

For example, if nums = [4,3,2,7,8,2,3,1], the output should be [5,6]. If nums = [1,1], the output should be [2]. Aim for linear time and minimal extra space when possible, though using a hash table simplifies the initial solution.

Examples

Example 1

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

Output: [5,6]

Example details omitted.

Example 2

Input: nums = [1,1]

Output: [2]

Example details omitted.

Constraints

n == nums.length
1 <= n <= 105
1 <= nums[i] <= n

Solution Approach

Hash Table Tracking

Create a hash table or set to record all numbers seen while iterating over nums. Then scan the full range [1, n] and collect numbers missing from the set. This ensures correctness with simple implementation and clear failure detection if a number is repeated.

In-place Negation Marking

Iterate through nums and for each number, mark its corresponding index as negative. In a second pass, positive indices indicate missing numbers. This avoids extra memory and leverages the input array for marking.

Optimized Counting Array

Use an auxiliary array of size n to count occurrences of each number. After filling counts, collect indices with zero occurrences. This variant explicitly tracks duplicates and missing numbers, exposing array scanning failure modes if indexing is mishandled.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for a single pass through nums and an additional pass for collecting missing numbers. Space complexity ranges from O(n) using hash tables or counting arrays to O(1) using in-place marking, exposing trade-offs between memory usage and simplicity.

What Interviewers Usually Probe

Expect a linear time solution without sorting.
Check if the candidate considers in-place marking to save space.
Look for clarity in handling duplicates and missing indices.

Common Pitfalls or Variants

Common pitfalls

Incorrectly assuming all numbers appear exactly once, missing duplicates.
Failing to handle the full range [1, n], especially the first or last elements.
Using excessive memory or unnecessary sorting instead of direct scanning.

Follow-up variants

Return missing numbers in a sorted array instead of original order.
Find missing numbers when array contains numbers outside [1, n].
Handle streaming input where nums is too large to fit in memory at once.

FAQ

What is the best approach for finding all missing numbers in an array?

Use a hash set to track seen numbers or mark indices in-place. Both approaches expose the array scanning plus hash lookup pattern.

Can this problem be solved without extra memory?

Yes, by using in-place negation marking, you can identify missing numbers without additional data structures.

How do duplicates affect the solution?

Duplicates require careful marking to avoid false negatives; using a set or in-place marking handles repeated elements correctly.

Is sorting a viable solution?

Sorting works but increases time complexity to O(n log n) and misses the efficiency of direct array scanning or hash lookup.

Why is this problem categorized under Array and Hash Table patterns?

Because the core solution involves scanning the array while using hash-based tracking to detect missing values efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        s = set(nums)
        return [x for x in range(1, len(nums) + 1) if x not in s]

Solution 2

#### Python3

1

2

3

4

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        s = set(nums)
        return [x for x in range(1, len(nums) + 1) if x not in s]

Continue Practicing

#447 number of boomerangs #442 find all duplicates in an array #454 4sum ii