Find All Numbers Disappeared in an Array

ArrayHash Table

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of the array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in the array.

Example 1

Input

[
  4,
  3,
  2,
  7,
  8,
  2,
  3,
  1
]

Output

[5,6]

Explanation. 5 and 6 do not appear in the input array.

Example 2

Input

[
  1,
  1
]

Output

[2]

Explanation. 2 does not appear in the input array.

Example 3

Input

[
  1,
  2,
  3,
  4,
  5
]

Output

[]

Explanation. All numbers from 1 to 5 appear in the input array.

Follow-up: Can you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Constraints:

1. Length of the array is in the range `[1, 10000]`.\n2. The integers in the array are in the range `[1, n]`, where `n` is the array size.

Views: 4