trjhtr

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 ]

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;

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

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;