finding all missing elements in an array/range javascript

Question

I am trying to to write a function to find all missing elements in an array. The series goes from 1...n. the input is an unsorted array and the output is the missing numbers.

below is what I have so far:

function findMissingElements(arr) {
  arr = arr.sort();
  var missing = [];

  if (arr[0] !== 1) {
    missing.unshift(1);
  }
  // Find the missing array items
  for (var i = 0; i < arr.length; i++) {

    if ((arr[i + 1] - arr[i]) > 1) {
      missing.push(arr[i + 1] - 1);
    }

  }
  return missing;
}

var numbers = [1, 3, 4, 5, 7, 8]; // Missing 2,6
var numbers2 = [5, 2, 3]; //missing 1, 4
var numbers3 = [1, 3, 4, 5, 7]; // Missing 2,6
console.log(findMissingElements(numbers)); // returns 2,6 correct
console.log(findMissingElements(numbers2)); // returns 1,4
console.log(findMissingElements(numbers3)); // returns 2, 6

I "manually" checked for the first element with an if block, is there any way to handle the case of the first element inside the for loop?

var numbers3 = [1, 3, 4, 5, 7]; // Missing 2,6,8 Why on earth do you say that 8 is missing? As far as we are concerned, the array is 1...7. — Maria Ines Parnisari
– Maria Ines Parnisari, Commented Dec 7, 2015 at 22:39
If you skip two numbers in a row your function will only output the second. — Phil Dornfeld
– Phil Dornfeld, Commented Dec 7, 2015 at 22:48

Mike Cluck · Accepted Answer · 2015-12-07 22:46:56Z

5

You can produce that by tracking which number should appear next and adding it to a list of missing numbers while it is less than the next number.

function findMissingElements(arr) {
  // Make sure the numbers are in order
  arr = arr.slice(0).sort(function(a, b) { return a - b; });
  let next = 1; // The next number in the sequence
  let missing = [];
  for (let i = 0; i < arr.length; i++) {
    // While the expected element is less than
    // the current element
    while (next < arr[i]) {
      // Add it to the missing list and
      // increment to the next expected number
      missing.push(next);
      next++;
    }
    next++;
  }
  return missing;
}

answered Dec 7, 2015 at 22:46

Mike Cluck

32.6k13 gold badges84 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

devdropper87 Over a year ago

thanks I'm going to check this out now. any particular reason for using 'let'?

DrakaSAN Over a year ago

let is about scoping, if I m not mistaken, it permit higher function to see next and missing.

Mike Cluck Over a year ago

@devdropper87 No reason. It's a new feature in ES6 that I've started using a lot. If you find that you're getting a syntax error in your chosen environment, you can safely change those to var. See MDN for more information on let.

devdropper87 Over a year ago

I tried to change the while to an if out of curiousity. why does it need a 'while' - so it doesn't just look at the first missing one if there's more than one missing in a row?

Mike Cluck Over a year ago

@devdropper87 Exactly. So if you're missing 2 - 5, for example, it doesn't just pick up 2 then compare 3 against 6.

lex82 · Accepted Answer · 2015-12-07 22:54:43Z

3

A not so efficient but more intuitive solution:

var n = Math.max.apply(null, arr);  // get the maximum
var result = [];
for (var i=1 ; i<n ; i++) {
    if (arr.indexOf(i) < 0) result.push(i)
}

answered Dec 7, 2015 at 22:54

lex82

11.4k2 gold badges48 silver badges72 bronze badges

1 Comment

Andy Over a year ago

Exactly the answer I was writing :)

shennan · Accepted Answer · 2015-12-07 22:54:34Z

1

Aside from the fact that your tests are not consistent, this feels a bit neater to me:

function findMissingElements (arr, fromFirstElement) {
 
  arr.sort();
  
  var missing = [];
  var next = fromFirstElement ? arr[0] : 1;
  
  while(arr.length) {
    var n = arr.shift();
    while (n != next) {
     missing.push(next++); 
    }
    next++;
  }
  
  return missing;
  
}

var numbers = [1, 3, 4, 5, 7, 8]; // Missing 2,6
var numbers2 = [5, 2, 3]; // Missing 1, 4
var numbers3 = [1, 3, 4, 5, 7]; // Missing 2, 6

console.log(findMissingElements(numbers)); // returns 2, 6
console.log(findMissingElements(numbers2)); // returns 1, 4
console.log(findMissingElements(numbers3)); // returns 2, 6

I've added an argument fromFirstElement which, if passed true, will enable you to start from a number defined by the first element in the array you pass.

edited Dec 7, 2015 at 22:54

answered Dec 7, 2015 at 22:47

shennan

11.8k5 gold badges52 silver badges94 bronze badges

2 Comments

lex82 Over a year ago

Cited from the question: The series goes from 1 to n

shennan Over a year ago

@lex82 right you are; have adjusted for the dual purpose.

Collectives™ on Stack Overflow

finding all missing elements in an array/range javascript

3 Answers 3

5 Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related