5
\$\begingroup\$

Is it possible to make this faster? Any suggestions are more than welcome

I have used JavaScript to write this code

PROBLEM

  • You will get an array of numbers.

  • Every preceding number is smaller than the one following it.

  • Some numbers will be missing, for instance:

      [-3,-2,1,5] // missing numbers are: -1,0,2,3,4
    

Your task is to return an array of those missing numbers:

[-1,0,2,3,4]

SOLUTION

const findTheMissing = (target) => {

    // final result list
    let result = [];

    // array will go from min to max value present in the array
    const min = target[0];
    const max = target[target.length - 1];

    // will maintain the track of index of target array
    // will start from 2nd element of array because we need a no. to subsctract from
    let pivotIndex = 1;

    for (let index = min; index < max; index++) {

        // value to the index
        let pivotValue = target[pivotIndex];

        // dif of the value
        let diff = pivotValue - index;

        // diff means its time to move the pivot to next :P
        if (diff > 0) {
            // not going to current index at exists in the target array
            if (index === target[pivotIndex - 1])
                index++;

            // YO!! WE FOUND HE MISSING
            result.push(index);
        }
        else {
            pivotIndex++;
        }
    }
    return result; // got all missing numbers
}

RESULT

let source = [-5, 0, 2, 5, 7];
console.log(findTheMissing(source));
// [ -4, -3, -2, -1, 2, 3, 4, 6 ]
\$\endgroup\$
3
  • 1
    \$\begingroup\$ what is your current benchmark? \$\endgroup\$
    – Malachi
    Commented Apr 16, 2018 at 13:47
  • \$\begingroup\$ @Malachi Number of iterations. The lesser the better \$\endgroup\$ Commented Apr 17, 2018 at 5:25
  • \$\begingroup\$ how did you run your test to benchmark your code? \$\endgroup\$
    – NinjaG
    Commented Apr 22, 2018 at 5:48

3 Answers 3

4
\$\begingroup\$

I think, there is an error:

If I enter the values:

[-3,-2,1,5]

I get the result:

[-2,0,2,3,4]

but it should be:

[-1,0,2,3,4]

The error occurs when there are two adjacent numbers in the array (here -3 and -2).


Naming:

Index is not an index, but the actual value in the valid sequence (from min to max). I would call it value or curValue or something like that.

I don't like the name target either, because the target is actually the sequence of numbers from min to max. input would be better IMO.


Analysis

Basically you want to compare two sequences of numbers index by index. If they differ then save the target value, if not then increment to the next value of the input array. The index of the target sequence (here from min to max) is always incremented. Instead of the target sequence you can just increment a value starting from input[0] and ending on input.[input.length - 1].

All in all it could be done something like this:

function findMissing(input) {

  var result = [];

  for (var inputIndex = 0, targetValue = input[0]; targetValue <= input[input.length - 1]; targetValue++) {
    if (input[inputIndex] != targetValue) {
      result.push(targetValue);
    }
    else {
      inputIndex++;
    }
  }

  return result;
}
\$\endgroup\$
1
\$\begingroup\$

Foreknowledge of result length

This type of problem has a short cut because you can know the size of the resulting array by just inspecting the first and last items. You can then use the calculated result length as an exit condition.

In the best result you only have to inspect the first and last value and exit without iteration if there are no missing values.

The worst you will have to count over all the values in between the first and last.

The resulting algorithm is very efficient

function missing(arr) {
    const result = [];
    if (arr.length <= 1) { return result }
    var i = 1, val = arr[0] + 1;
    const count = ((arr[arr.length - 1]) - val) - (arr.length - 2);
    while (result.length < count) {
        while (arr[i] !== val) { result.push(val++) }
        i++;
        val++;
    }
    return result;
}

The snippet shows the number of iterations to find the missing values.

var iterations;
function missing(arr) {
    var ic = 0;        // iteration counter
    const result = [];
    if (arr.length <= 1) { return result }
    var i = 1, val = arr[0] + 1;
    const count = ((arr[arr.length - 1]) - val) - (arr.length - 2);
    while (result.length < count) {
        ic = 0;
        while (arr[i] !== val) { 
          result.push(val++) 
          ic ++;  // Count once for each inner iteration step
        }
        i++;
        val++;
        iterations += ic ? ic : 1; // count inner or one for outer loop
    }
    return result;
}

function doIt(arr){
    iterations = 0;
    console.log("Array [" + arr.join("") + "] missing ["+ missing(arr).join("") + "] in " + iterations + " iterations.");
}

doIt([0,9])    
doIt([0,2,3,8,9])
doIt([0,2,3,6,8,9])     
doIt([0,2,4,5,6,7,8,9])       
doIt([0,2,3,4,5,6,7,8,9])      
doIt([0,1,2,3,4,5,6,7,9])    
doIt([0,1,2,3,4,5,6,7,8,9])

\$\endgroup\$
-2
\$\begingroup\$

No rocket science:

  • Do Lesser operations and your program is faster
  • No Loop inside Loops and Time complexity is less
  • Don't initialize variables in a loop instead assign them in variables out of loop
  • Enhance readability using KISS
  • Use Bit-wise operators and gain more speed, I haven't used

CODE

function findMissingNumbers(array) {
    const arraySize = array.length;
    const arr = [];
    let i = 0;
    let j = array[0];
    let jSize = array[arraySize - 1];
    while (j < jSize) {
        (array[i] === j) ? (i += 1) : (arr.push(j));
        j++;
    }
    return arr;
}
\$\endgroup\$
4
  • \$\begingroup\$ What exactly you want to understand. \$\endgroup\$ Commented Apr 16, 2018 at 11:39
  • 3
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$
    – Martin R
    Commented Apr 16, 2018 at 13:02
  • \$\begingroup\$ @MartinR please check now. Hope i am able to keep it clean and simple. :) \$\endgroup\$ Commented Apr 16, 2018 at 14:00
  • 2
    \$\begingroup\$ While your points here helps a bit, it is not always entirely correct and it's not clear how you arrived at the smaller code. By the way, the original code did not have any loops inside loops. \$\endgroup\$ Commented Apr 16, 2018 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.