How to write the code with less time complexity for finding the missing element in given array range?

Question

My function should return the missing element in a given array range. So i first sorted the array and checked if the difference between i and i+1 is not equal to 1, i'm returning the missing element.

// Given an array A such that:
// A[0] = 2
// A[1] = 3
// A[2] = 1
// A[3] = 5
// the function should return 4, as it is the missing element.

function solution(A) {
  A.sort((a,b) => {
    return b<a;
  })
  var len = A.length;
  var missing;
  for( var i = 0; i< len; i++){
    if( A[i+1] - A[i] >1){
      missing = A[i]+1;
    }
  }
  return missing;
}

I did like above, but how to write it more efficiently??

Answer 1

You could use a single loop approach by using a set for missing values.

In the loop, delete each number from the missing set.

If a new minimum value is found, all numbers who are missing are added to the set of missing numbers, except the minimum, as well as for a new maximum numbers.

The missing numbers set contains at the end the result.

function getMissing(array) {
    var min = array[0],
        max = array[0],
        missing = new Set;
    
    array.forEach(v => {
        if (missing.delete(v)) return;                   // if value found for delete return
        if (v < min) while (v < --min) missing.add(min); // add missing min values
        if (v > max) while (v > ++max) missing.add(max); // add missing max values
    });
    return missing.values().next().value;                // take the first missing value
}

console.log(getMissing([2, 3, 1, 5]));
console.log(getMissing([2, 3, 1, 5, 4, 6, 7, 9, 10]));
console.log(getMissing([3, 4, 5, 6, 8]));

Answer 2

Well, from the question (as it's supposed to return a single number) and all the existing solution (examples at least), it looks like list is unique. For that case I think we can sumthe entire array and then subtracting with the expected sum between those numbers will generate the output.

sum of the N natural numbers

1 + 2 + ....... + i + ... + n we can evaluate by n * (n+1) / 2

now assume, in our array min is i and max is n

so to evaluate i + (i+1) + ..... + n we can

A = 1 + 2 + ..... + (i-1) + i + (i+1) + .... n (i.e. n*(n+1)/2)

B = 1 + 2 + ..... + (i-1) and

C = A - B will give us the sum of (i + (i+1) + ... + n)

Now, we can iterate the array once and evaluate the actual sum (assume D), and C - D will give us the missing number.

Let's create the same with each step at first (not optimal for performance, but more readable) then we will try to do in a single iteration

let input1 = [2, 3, 1, 5],
    input2 = [2, 3, 1, 5, 4, 6, 7, 9, 10],
    input3 = [3, 4, 5, 6, 8];

let sumNatural = n => n * (n + 1) / 2;

function findMissing(array) {
  let min = Math.min(...array),
      max = Math.max(...array),
      sum = array.reduce((a,b) => a+b),
      expectedSum = sumNatural(max) - sumNatural(min - 1);
      return expectedSum - sum;
}

console.log('Missing in Input1: ', findMissing(input1));
console.log('Missing in Input2: ', findMissing(input2));
console.log('Missing in Input3: ', findMissing(input3));

Now, lets try doing all in a single iteration (as we were iterating 3 times for max, min and sum)

let input1 = [2, 3, 1, 5],
    input2 = [2, 3, 1, 5, 4, 6, 7, 9, 10],
    input3 = [3, 4, 5, 6, 8];

let sumNatural = n => n * (n + 1) / 2;

function findMissing(array) {
  let min = array[0],
      max = min,
      sum = min,
      expectedSum;
  // assuming the array length will be minimum 2
  // in order to have a missing number
  for(let idx = 1;idx < array.length; idx++) {
    let each = array[idx];
    min = Math.min(each, min); // or each < min ? each : min;
    max = Math.max(each, max); // or each > max ? each : max;
    sum+=each; 
  }

  expectedSum = sumNatural(max) - sumNatural(min - 1);
  return expectedSum - sum;
}

console.log('Missing in Input1: ', findMissing(input1));
console.log('Missing in Input2: ', findMissing(input2));
console.log('Missing in Input3: ', findMissing(input3));

Answer 3

Instead of sorting, you could put each value into a Set, find the minimum, and then iterate starting from the minimum, checking if the set has the number in question, O(N). (Sets have guaranteed O(1) lookup time)

const input1 = [2, 3, 1, 5];
const input2 = [2, 3, 1, 5, 4, 6, 7, 9, 10];
const input3 = [3, 4, 5, 6, 8];

function findMissing(arr) {
  const min = Math.min(...arr);
  const set = new Set(arr);
  return Array.from(
    { length: set.size },
    (_, i) => i + min
  ).find(numToFind => !set.has(numToFind));
}
console.log(findMissing(input1));
console.log(findMissing(input2));
console.log(findMissing(input3));

Answer 4

If the array is items and the difference between missing and present diff is 1:

const missingItem = items => [Math.min(...items)].map(min => items.filter(x =>
    items.indexOf(x-diff) === -1 && x !== min)[0]-diff)[0]

would give complexity of O(n^2).

It translates to: find the minimum value and check if there isn't a n-diff value member for every value n in the array, which is also not the minimum value. It should be true for any missing items of size diff.

To find more than 1 missing element:

([Math.min(...items)].map(min => items.filter(x =>
    items.indexOf(x-diff) === -1 && x !== min))[0]).map(x => x-diff)

would give O((m^2)(n^2)) where m is the number of missing members.

Answer 5

Found this old question and wanted to take a stab at it. I had a similar thought to https://stackoverflow.com/users/2398764/koushik-chatterjee in that I think you can optimize this by knowing that there's always only going to be one missing element. Using similar methodology but not using a max will result in this:

function getMissing(arr) {
    var sum = arr.reduce((a, b) => a + b, 0);
    var lowest = Math.min(...arr);
    var realSum = (arr.length) * (arr.length + 1) / 2 + lowest * arr.length;
    return realSum - sum + lowest;
}

With the same inputs as above. I ran it in jsperf on a few browsers and it is faster then the other answers.

https://jsperf.com/do-calculation-instead-of-adding-or-removing.

First sum everything, then calculate the lowest and calculate what the sum would be for integers if that happened to be the lowest. So for instance if we have 2,3,4,5 and want to sum them that's the same as summing 0,1,2,3 and then adding the lowest number + the amount of numbers in this case 2 * 4 since (0+2),(1+2),(2+2),(3+2) turns it back into the original. After that we can calculate the difference but then have to increase it once again by the lowest. To offset the shift we did.

Answer 6

You can use while loop as well, like below -

function getMissing(array) {
  var tempMin = Math.min(...array);
  var tempMax = tempMin + array.length;
  var missingNumber = 0;
  
  while(tempMin <= tempMax){
    if(array.indexOf(tempMin) === -1) {
       missingNumber = tempMin;
    }
    tempMin++;
  }
  return missingNumber;
}

console.log(getMissing([2, 3, 1, 5]));
console.log(getMissing([2, 3, 1, 5, 4, 6, 7, 9, 10]));
console.log(getMissing([3, 4, 5, 6, 8]));

Answer 7

My approach is based on in place sorting of the array which is O(N) and without using any other data structure.

1. Find the min element in the array.
2. Sort in place.
3. Again loop the array and check if any element is misplaced, that is the answer!

function getMissing(ar) {

    var mn = Math.min(...ar);
    var size = ar.length;

    for(let i=0;i<size;i++){
        let cur = ar[i];
        // this ensures each element is in its right place
        while(cur != mn +i && (cur - mn < size) && cur != ar[cur- mn]) {
            // swap
            var tmp = cur; 
            ar[i] = ar[cur-mn];
            ar[cur-mn] = tmp;
        }
    }

    for(let i=0; i<size; i++) {
        if(ar[i] != i+mn) return i+mn;
    }

}

console.log(getMissing([2, 3, 1, 5]));
console.log(getMissing([2, 3, 1, 5, 4, 6, 7, 9, 10]));
console.log(getMissing([3, 4, 5, 6, 8]));