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??

• Nina Scholz: please use a numerical value for sorting instead of a boolean, because you irritate the sorting algorithm because you miss the negative range for sorting.
• Adelin: Possible duplicate of How to efficiently check if a list of consecutive numbers is missing any elements

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]));

• Patrick Roberts: missing.values().next().value would avoid iterating the entire Set just to get the first value. Or for (const value of missing) return value would work as well.
• Rick: @NinaScholz could you also state the time complexity? I had no idea that Set had an iterator next() method on values() Mind is blown!
• Rick: @NinaScholz also the the space complexity as well :)
• Nina Scholz: @Rick, one for each element and max one for each element to fill left and right side. space in worst case less than O(n) which means one space for each element, time less than O(2n) which is O(n).
• VLAZ: @NinaScholz just a small clarification - the complexity is O(n) only when there is one missing element. For larger gaps, the relationship is different because those two loops will not be bound by the input size of the array. For example [1, 2, 9001] will produce a lot more operations than [1, 2, 4]. The complexity is O(n*m) worst case scenario where m is the largest gap between the values. However, when m = 1 it can be ignored and it simplifies to O(n).

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));

• fafl: This is the only answer here that runs in O(n), finds the missing element in a single pass and does not need additional memory for some kind of set.

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));

• Nina Scholz: Math.min: first loop, set: second loop, Array.from: third loop, find final and fourth loop. anyway.

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]));