2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ does this work? console.log(findDisappearedNumbers([4,7,2,9])); yields [1,3]. The problem description is defective. \$\endgroup\$ – radarbob May 19 at 17:50
  • \$\begingroup\$ @radarbob 1 ≤ a[i] ≤ n (n = size of array). Your array [4,7,2,9] has to have at least the size of 9. \$\endgroup\$ – thadeuszlay May 19 at 18:09
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Finally I received a praise from you :p. J/k. Btw: don’t mind that I use function expression instead of function statement. I copied from the original task \$\endgroup\$ – thadeuszlay May 20 at 14:33
  • \$\begingroup\$ @thadeuszlay Most points I make are what I consider good practice but there is only one right way and that is "does it work?", I will try not to harp on about points if people don't follow or disagree. Did I give praise WTF.... lol... I think you are developing your skills very well. \$\endgroup\$ – Blindman67 May 20 at 14:41
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.