Show problems as
Classic problem #448EasyArrayHash Table

Find All Numbers Disappeared in an Array

Real-world version: Bibs the Mat Never Saw
Tracked in this browser only
Read Find All Numbers Disappeared in an Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A fun run gives out bibs numbered 1 through n, one per runner, and a timing mat at the finish writes one line into its log for every runner who crosses. So nums holds exactly n readings, and every reading is a bib number between 1 and n.

The mat is not perfect. It sometimes fires twice on the same bib and misses another one entirely, so a bib number may appear in nums several times while some bib numbers appear nowhere at all.

Return every bib number from 1 to n that does not appear in nums, listed in increasing order. Return an empty list when the mat caught them all.

The log may be reorganised in place; aim to answer in a number of steps proportional to n and without any working storage beyond the list you return.

Examples

Example 1

Input
nums = [3, 6, 1, 6, 3, 5]
Output
[2, 4]

Six bibs were given out. The log names 1, 3, 5 and 6, with 3 and 6 written twice, and never names 2 or 4.

Example 2

Input
nums = [1, 2, 3]
Output
[]

Each of the three bibs appears once, so nothing is missing.

Example 3

Input
nums = [2, 2]
Output
[1]

Two bibs were given out and the mat wrote bib 2 on both lines, so bib 1 is absent.

Example 4

Input
nums = [5, 5, 5, 5, 5]
Output
[1, 2, 3, 4]

Five bibs were given out and every line of the log reads 5, so bibs 1 through 4 never appear.

Constraints

  • n == nums.length
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_disappeared_numbers(nums: list[int]) -> list[int]:
Java
public List<Integer> findDisappearedNumbers(int[] nums)

More on the same topics