Three Missing Numbers

Given an unsorted list of n-3 distinct integers from 1..n, find the three missing numbers in ascending order.

arrays sets missing

You are given an unsorted list `nums` that contains exactly `len(nums)` distinct integers, all of which are in the range `1..n`, but **three** numbers from that range are missing. The value of `n` is `len(nums) + 3`. Write a function `find_missing_numbers(nums)` that returns a list of the three missing numbers in **ascending order**.

For example, if `nums = [2, 4, 1, 5]`, then `n = 4 + 3 = 7`. The numbers present are 1, 2, 4, 5. Missing are 3, 6, 7. So the function returns `[3, 6, 7]`.

Do not assume the list is sorted. The returned list must be sorted ascending. The function should have O(1) extra space beyond the input and output. You may modify the input list if needed.

Constraints

Input constraints:
- `len(nums) >= 1` (so `n >= 4`)
- `nums` contains distinct integers from `1..n` where `n = len(nums) + 3`
- Exactly three numbers from `1..n` are missing.
- Time complexity: O(n) is acceptable. Space complexity: O(1) extra space (output not counted).

Example

>>> find_missing_numbers([2, 4, 1, 5])
[3, 6, 7]
>>> find_missing_numbers([1, 2, 3, 4])
[5, 6, 7]
>>> find_missing_numbers([5, 4, 3, 2, 1, 8, 10, 9])
[6, 7, 11]

15 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Calculate n = len(nums) + 3. Think about the total sum or set difference.

Instead of a separate set, you can use a boolean list of size n+1 to mark present numbers.

If you want O(1) extra space, consider marking visited numbers by negating the value at index `value-1`.

After marking, scan indices from 0 to n-1 and collect indices where the value is still positive (or non-marked).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.