What pattern does Find All Numbers Disappeared in an Array use?

The Pattern: In-place Marking via Index Negation The Heuristic: Use the input array as a presence marker by negating values at indices corresponding to seen numbers, enabling O(1) extra space detection of missing elements.

Find All Numbers Disappeared in an Array

Q: What is the time complexity of Find All Numbers Disappeared in an Array?

O(n). The algorithm makes two passes over the array: one to mark presence and one to collect missing numbers, each O(n).

Problem

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.

n == nums.length
1 ≤ n ≤ 10⁵
1 ≤ nums[i] ≤ n

Example

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

Output: [5,6]

The array length is 8, so the numbers 1 through 8 should appear. The input contains 1,2,2,3,3,4,7,8. Numbers 5 and 6 are missing. The algorithm marks visited numbers by negating the value at the index corresponding to each number's value minus one. After marking, positive values indicate missing numbers at those indices plus one.

Approach

Straightforward Solution

A naive approach uses a hash set to record all numbers seen and then iterates from 1 to n to find missing numbers. This requires O(n) time but O(n) extra space, violating the space constraint.

Core Observation

Each number in nums is in the range [1, n], which means each number can be mapped to an index in the array (number - 1). By marking the presence of a number at its corresponding index, the problem reduces to detecting which indices remain unmarked, indicating missing numbers.

Path to Optimal

Preview

The key insight is to use the input array itself as a marker structure. By negating the value at the index corresponding to each number encountered, the algorithm marks that number as present…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through nums, for each number num, compute index = abs(num) - 1 and negate nums[index] if it is positive. Then iterate through nums again; indices with positive values indicate missing numbers (index + 1)…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm makes two passes over the array: one to mark presence and one to collect missing numbers, each O(n).

Space

O(1)

The algorithm uses no extra data structures besides the output array, modifying the input array in place for marking.

Solution

Python

1class Solution:
2    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
3        for num in nums:
4            index = abs(num) - 1
5            nums[index] = -abs(nums[index])
6
7        missing_numbers = []
8
9        for index, num in enumerate(nums):
10            if num > 0:
11                missing_numbers.append(index + 1)
12
13        return missing_numbers

Step-by-Step Solution

1

Mark Numbers Present by Negating Corresponding Indices

3for num in nums:
4    index = abs(num) - 1
5    nums[index] = -abs(nums[index])

Objective

To mark each number's presence by negating the value at the index corresponding to that number minus one.

Key Insight

By using the absolute value of each number to find its corresponding index, the algorithm safely negates the value at that index to indicate presence without losing information. Using abs ensures that previously negated values do not interfere with the marking process. This in-place marking avoids extra space and leverages the problem's constraint that numbers are in [1, n].

Interview Quick-Check

Core Logic

Negate the value at index abs(num) - 1 to mark the number as seen, using absolute values to handle previously negated entries.

Common Pitfalls & Bugs

Failing to use abs(num) can cause incorrect indexing when values have already been negated.

State & Boundaries

Only negate if the value at the target index is positive to avoid double negation.

2

Collect Missing Numbers from Positive Indices

To identify indices with positive values after marking, which correspond to missing numbers, and collect them into the result list.

3

Return the List of Missing Numbers

To return the collected list of missing numbers as the final output.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 5 Critical

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

Negate the value at the calculated index if it is positive to mark the number as present.

Negating only positive values prevents double negation, which could revert the marking and cause incorrect results.

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

Why does negating the value at the index corresponding to a number's value correctly mark that number as present?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Find All Numbers Disappeared in an Array from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Find All Numbers Disappeared in an Array drill

or drill a free problem

1	`class Solution:`
2	`def findDisappearedNumbers(self, nums: List[int]) -> List[int]:`
3	`for num in nums:`
4	`index = abs(num) - 1`
5	`nums[index] = -abs(nums[index])`
6
7	`missing_numbers = []`
8
9	`for index, num in enumerate(nums):`
10	`if num > 0:`
11	`missing_numbers.append(index + 1)`
12
13	`return missing_numbers`