← DSA Atlas
Dedicated problem page · #448

Find All Numbers Disappeared in an Array

EasyArrays and HashingIn-place negation marking (index as hash)Array used as its own hash table
Solve on LeetCode ↗
448
EasyArrays and HashingArray used as its own hash tableIn-place negation marking (index as hash)

Find All Numbers Disappeared in an Array

Given an array nums of n integers where each value is in the range [1, n], return a list of all integers in [1, n] that do not appear in nums. Values may repeat, so some numbers in the range are missing.

Open official problem prompt ↗
In plain English

List every number in 1..n that is absent from an array whose values are confined to that same range.

Picture it like this

Imagine a hotel with rooms 1..n and a guest list. As you read each ticket you flip the 'occupied' flag on the matching room. When you are done, the rooms whose flag was never flipped are the empty ones.

Example
Input
nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output
[5, 6]
Why
n = 8, so the full range is 1..8. The values present are {1,2,3,4,7,8}; 5 and 6 never appear.
Constraints
n == nums.length1 <= n <= 10^51 <= nums[i] <= n
Pattern lesson

See the pattern, then code

In-place negation marking (index as hash)
Recognition clue

Values are bounded exactly to [1, n] and the array has length n, so each value maps naturally to an index. That one-to-one range-to-index mapping is the signal you can use the array itself as a presence table.

↗
Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. Seeing value v means index v-1 should be marked 'visited'. Flip the sign of nums[v-1] to record the visit without losing the original magnitude (recover it with abs). Any slot still positive at the end was never visited, so its index+1 is missing.

New words, made simpleKnow these before the algorithm
Sign as a flag
Using the sign bit of a slot to record a boolean 'seen' while abs() preserves the number stored there.
Index-as-hash
Mapping a value v directly to array position v-1, turning the array into an O(1) presence table.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Hash set of seen values

Correct and simple but uses extra O(n) memory the follow-up forbids.

Insert all values into a set, then check 1..n against it.

Time O(n)Space O(n)
Boolean seen[] array

Also linear extra space; the negation trick removes it.

Allocate a length-n boolean array and mark seen indices.

Time O(n)Space O(n)
Best choiceIn-place sign marking

Linear time with only constant extra space, meeting the follow-up.

Encode 'seen' into the sign of the existing array, then read off positive slots.

Time O(n)Space O(1)
The rule we keep true

Invariant

After processing, nums[i] < 0 if and only if the value i+1 appeared at least once in the original array.

Why this is correct

Reasoning

Every value v triggers a negation at index v-1, so a slot ends up negative exactly when its corresponding value was seen. Using abs(x) when reading a possibly-already-negated slot recovers the true value, so marks are never lost, and the guard against re-negation keeps a doubly-seen value from flipping back to positive.

The algorithm in three movesSay these aloud before coding
1For each value x, compute target index abs(x)-1

see 4 -> mark idx 3 negative

2If nums at that index is positive, negate it to mark the value present

see 2 (twice) -> idx 1 already negative

3After the pass, scan for slots that are still positive

slots 4 and 5 stay positive -> 5, 6 missing

4Collect index+1 for every positive slot

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
40
31
22
73
84
25
36
17
1 · Readx=4
2 · AskIs nums[3] positive?
3 · Update statenums[3]=7 -> -7
4 · ResultMark value 4 present
Key takeaway

Slots 5 and 6 (values 8 and 2) were never used as a target index, so they stay positive and reveal the missing numbers 5 and 6.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-6Mark presence

    abs(x)-1 finds the slot for value x; negating it records 'seen', and the positivity guard avoids flipping a value marked twice back to positive.

  2. 2
    Lines 7Collect the missing

    Any slot still positive was never targeted, so its index+1 is a number that never appeared.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • No numbers missing (every value 1..n present) -> return []
  • All duplicates of one value, e.g. [1,1,...] -> everything except 1 is missing
  • n = 1 with nums = [1] -> return []
!

Common beginner mistakes

  • Reading nums[i] directly instead of abs(nums[i]) to compute the target index once a slot has already been negated
  • Negating without the positivity guard, which flips doubly-seen values back to positive and corrupts the result
  • Assuming values are 0-indexed; they are 1..n so the mapping is value-1
  • Mutating the input when the caller needs it preserved (acceptable here, but worth noting)
Check your understanding

Why do we take abs(x) before computing the index inside the loop?

More in Arrays and Hashing

#1Two SumComplement lookup#49Group AnagramsCanonical key bucketing#238Product of Array Except SelfPrefix and suffix products#128Longest Consecutive SequenceSequence-start expansion#560Subarray Sum Equals KPrefix-sum complement count#36Valid SudokuConstraint tracking with sets