Find All Numbers Disappeared in an Array

Question

The task is taken from leetcode

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

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

Example:

Input:

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

Output:

[5,6]

My solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
  return nums
    .reduce((arr, x) => {
      arr[x - 1] = null;
      return arr;
    }, Array.from({length: nums.length}, (v, k) => k+1))
    .filter(Boolean);
};

There has to be a more elegant solution to that.

Answer 1

You have created a good solution, just a few style points that can reduce code size.

• Why null rather than false or even 0 in arr[x - 1] = null;

• Why not use commas to remove need for return. Eg .reduce((arr, x) => {arr[x - 1] = null; return arr; } becomes .reduce((arr, x) => (arr[x - 1] = null, arr))

• To create an array of indexes you could have used the shorter forms, Array.from(nums, (item, i) => i + 1)) or nums.map((item,i) => i + 1)

Rewrites

function findMissing(arr) {
  return arr
    .reduce((a, i) => (a[i - 1] = 0, a), arr.map((item, i) => i + 1))
    .filter(Boolean);
}

or

const findMissing = arr => arr
  .reduce((a, i) => (a[i - 1] = 0, a), arr.map((item, i) => i + 1))
  .filter(Boolean);

You could also have solved it with a set as follows

function findMissing(arr) {
    const s = new Set(arr), res = [];
    var i = arr.length;
    while (i) { s.has(i--) || res.push(i + 1) }
    return res;
}

Answer 2

Could you do it without extra space and in \$O(n)\$ runtime?

The implementation uses \$O(n)\$ extra space. A different approach is possible without extra space, by rearranging the content of the input array, so that the values that appear ordered, and at the position where they would be if nothing was missing.

Going with the example [4,3,2,7,8,2,3,1], the content can be rearranged in \$O(n)\$ time to become this:

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

Then, with one more pass, you can identify [5, 6] as the missing pieces.