How to write the code with less time complexity for finding the missing element in given array range?
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]));
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 sum
the 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));
Instead of sort
ing, 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));