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


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