Find All Numbers Disappeared in Array

EasyArrays & Hashingindex marking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an integer array nums of length n, where every value is guaranteed to fall in the inclusive range [1, n]. Because the array has n slots but values may repeat, some numbers from 1 to n may never appear at all. Return a list of all the integers in the range [1, n] that are **missing** from nums. The order of the returned values does not matter. For example, if n = 5 and nums = [4, 3, 2, 7, ...] style data is given, you would scan which of 1..n never show up and collect them. **Follow-up:** Can you solve this without allocating extra space for another data structure (the output list does not count as extra space) and in O(n) time? A common trick is *index marking*: use the values themselves to flag, inside the same array, which positions have been "seen".

Examples

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
Here n = 8, so the full range is 1..8. The values 5 and 6 never appear in the array, while every other number does.
Input: nums = [1,1]
Output: [2]
n = 2, range is 1..2. The value 1 appears twice and 2 is absent, so 2 is the only missing number.
Input: nums = [1,2,3,4,5]
Output: []
Every number from 1 to 5 is present exactly once, so nothing is missing.

Constraints

  • `n == nums.length`
  • `1 <= n <= 10^5`
  • `1 <= nums[i] <= n`
  • The returned order does not matter.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More index marking problems