LeetCode: Find All Numbers Disappeared in an Array Solution

Approach

Use hash table (Set) as existing reference

Implementation

1/**
2 * @param {number[]} nums
3 * @return {number[]}
4 */
5var findDisappearedNumbers = function (nums) {
6  const set = new Set(nums)
7  const res = []
8
9  for (let num = 1; num <= nums.length; num++) {
10    if (set.has(num) === false) {
11      res.push(num)
12    }
13  }
14
15  return res
16}

O(1) memory approach

Different existence marking strategy:

• use index-based to mark the existence of a number (eg. for number 4 to exist, use index 3 to mark)
• transfrom nums array to existence checking array
• if a number is existed, the array value at its index-based will be negative

1For array
2[4, 3, 2, 7, 8, 2, 3, 1]
3
4Transformation
5[ 4,  3,  2, -7,  8,  2,  3,  1]
6[ 4,  3, -2, -7,  8,  2,  3,  1]
7[ 4, -3, -2, -7,  8,  2,  3,  1]
8[ 4, -3, -2, -7,  8,  2, -3,  1]
9[ 4, -3, -2, -7,  8,  2, -3, -1]
10[ 4, -3, -2, -7,  8,  2, -3, -1]
11[ 4, -3, -2, -7,  8,  2, -3, -1]
12[-4, -3, -2, -7,  8,  2, -3, -1]

Implementation

1/**
2 * @param {number[]} nums
3 * @return {number[]}
4 */
5var findDisappearedNumbers = function (nums) {
6  for (const num of nums) {
7    const i = Math.abs(num) - 1
8    nums[i] = -Math.abs(nums[i])
9    // console.log(nums) // use this to see how things work
10  }
11
12  return nums.map((num, i) => (num < 0 ? 0 : i + 1)).filter(Boolean)
13}