Find All Numbers Disappeared in an Array — Solution

Problem

You're given an array of n integers where every value falls in the range [1, n]. Because of duplicates, some numbers in that range never appear. Return a list of all the missing ones.

• Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
• Output: [5, 6]
• Explanation: The array has length 8, so the full range is 1–8; the numbers 5 and 6 never appear.

Counter-example: nums = [1, 1] → output [2], because 2 is never seen and 1 appears twice.

Intuition

Every value in the array is a valid 1-based index into that same array. That means you can use the values themselves to leave a mark — without any extra storage — by negating the element at the corresponding position. After one pass, any index whose value is still positive points to a number that was never visited.

Approach 1 — Hash Set

Store every number seen in a set, then sweep 1 through n to collect anything absent.

1. Add all elements of nums to a hash set.
2. Iterate i from 1 to n (inclusive).
3. If i is not in the set, append it to the result.
4. Return the result list.

1def findDisappearedNumbers(nums: list[int]) -> list[int]:
2    seen = set(nums)
3    return [num for num in range(1, len(nums) + 1) if num not in seen]

Time: O(n) — one pass to build the set, one pass to find gaps.
Space: O(n) — the hash set holds up to n distinct values.

Approach 2 — In-Place Index Marking

Use the array itself as a visited map by negating the element at index abs(num) - 1 for every number encountered. Indices that remain positive after the full pass correspond to missing numbers.

1. For each num in nums, compute index = abs(num) - 1 (use abs because a prior iteration may have already negated this slot).
2. If nums[index] is positive, negate it to mark that value as seen.
3. After the loop, iterate through nums with index i.
4. If nums[i] > 0, the value i + 1 was never encountered — add it to the result.
5. Return the result list.

1def findDisappearedNumbers(nums: list[int]) -> list[int]:
2    for num in nums:
3        index = abs(num) - 1          # recover original value even if already negated
4        if nums[index] > 0:
5            nums[index] = -nums[index] # mark this slot as visited
6
7    # slots still positive were never marked — their 1-based index is missing
8    return [i + 1 for i, val in enumerate(nums) if val > 0]

Time: O(n) — two linear passes over the array.
Space: O(1) — the marking is done in-place; the output list is not counted.

Complexity Summary

Common Mistakes

• Reading num directly as an index instead of abs(num) — a duplicate value may have already been negated in an earlier iteration, so you must take the absolute value before using it as an index.
• Negating without checking the sign first — if a slot is already negative and you negate it again you restore it to positive, incorrectly un-marking a visited number.
• Off-by-one on the index — values are 1-based but arrays are 0-based, so the index is abs(num) - 1, not abs(num).
• Returning i instead of i + 1 — the final pass collects 0-based indices, but the answer requires 1-based missing values.
• Allocating a separate boolean array — a visited[n] array has the same O(n) space cost as the hash set; the whole point of the in-place approach is to avoid that extra allocation entirely.

Related Problems

• find-all-duplicates-in-an-array — identical negation trick, but you collect indices marked twice instead of those never marked
• first-missing-positive — harder variant: find the smallest missing positive with the same O(1)-space constraint
• missing-number — find the single missing value in [0, n]; simpler but the same "values-as-indices" thinking
• contains-duplicate — detect whether any value appears more than once, a prerequisite intuition for this problem
• find-the-duplicate-number — uses cycle detection or index marking to find a repeated value in [1, n]