Every Vanished Number

EasyArrays & Hashing

Problem

An inventory scan of n shelves should have read each product code 1 to n once, but the scanner sometimes reads a code twice, so some codes never appear. nums holds the n scanned codes.

Return every code in 1..n that does not appear in nums, in ascending order. Use O(1) extra space besides the output; you may modify nums.

Example 1

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

n = 8; codes 5 and 6 never appear.

Example 2

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

Constraints

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

Hint

Show the first hint

Each code v has a home slot v - 1 in the same array.

Walkthrough

How to approach it

01Clarify before coding

  • Can a code appear more than twice? Yes; marking must be idempotent (only make negative, never toggle).
  • Does the output count as extra space? No.
  • Order of the output? Ascending, which the index scan gives for free.

02Brute force

For each v in 1..n, scan nums to see if it is present; or use a set or boolean array.

Cost: Scanning: O(n²) time. A set or boolean array: O(n) time but O(n) extra space.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.