easy

Find All Numbers Disappeared in an Array

Find every number missing from a 1..n ranged array, in place.

1. Define the problem

Find All Numbers Disappeared in an Array

Given an array nums of n integers where each numsi is in the range [1, n], return an array of all the integers in that range that do not appear in nums. Since every value must fall between 1 and n, use each value as an index into the array itself — mark the position it points to as seen (for example, by flipping its sign) — so that any position never marked reveals a missing number, without extra memory.

Constraints

  • n == nums.length
  • 1 ≤ n ≤ 105
  • 1 ≤ numsi ≤ n

Example

Inputnums = [4, 3, 2, 7, 8, 2, 3, 1]
Output[5, 6]

Explanation 5 and 6 are the only numbers between 1 and 8 that never appear in nums.

2. Know the words first

In plain terms

Index into the array itself
Using a value from the array as a position within that same array, instead of storing seen values in a separate structure.
3. Visualize the solution

Mark visited positions by flipping the sign

Mark visited positions by flipping the sign
Statusinit

value=4 -> mark index 3 negative.

What happens in this step

value = nums[0] = 4
target index = 4 - 1 = 3

Flip nums[3] to negative to mark 4 as seen.
Step 1 of 4

Steps to visualize

  1. Walk through nums; for each value v, compute the index v - 1.
  2. Make nums[v - 1] negative to mark that position as visited (if not already negative).
  3. After one pass, any index still holding a positive value means that index + 1 never appeared.
  4. Collect index + 1 for every position still positive.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Mark visited positions by flipping the sign
Statusinit

value=4 -> mark index 3 negative.

What happens in this step

value = nums[0] = 4
target index = 4 - 1 = 3

Flip nums[3] to negative to mark 4 as seen.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function findDisappearedNumbers(nums) {
  const arr = nums.slice();

  for (let i = 0; i < arr.length; i++) {
    const targetIndex = Math.abs(arr[i]) - 1;

    if (arr[targetIndex] > 0) {
      arr[targetIndex] = -arr[targetIndex];
    }
  }

  const missing = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > 0) {
      missing.push(i + 1);
    }
  }

  return missing;
}
Time
O(n)
Space
O(1) extra (excluding the output array)
6. Test cases

Test cases

InputExpectedCovers
nums = [4, 3, 2, 7, 8, 2, 3, 1][5, 6]example from the docstring
nums = [1, 2, 3, 4][]every number from 1 to n appears, nothing missing
nums = [1, 1][2]every element is the same value, most numbers missing
nums = [1][]smallest valid input, a single element with nothing missing
nums = [3, 2, 1][]values present but out of order, nothing missing
nums = [2, 2, 2, 2][1, 3, 4]multiple distinct numbers missing at once

Keep reading