How to efficiently check if a list of consecutive numbers is missing any elements

Question

I have this array

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];

I was trying to find an algorithm that will tell me which ss are missing. As you can see, the list consists of consecutive ss (s1, s2, etc.).

At first I went with this solution:

    var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];
for (var i=1;i<arr.length;i++){
    var thisI = parseInt(arr[i].toLowerCase().split("s")[1]);
    var prevI = parseInt(arr[i-1].toLowerCase().split("s")[1]);
    if (thisI != prevI+1)
      console.log(`Seems like ${prevI+1} is missing. thisI is ${thisI} and prevI is ${prevI}`)
}

But this method fails for more than one consecutive numbers missing (s15, s16). So I added a while loop which works.

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];
for (var i=1;i<arr.length;i++){
  var thisI = parseInt(arr[i].toLowerCase().split("s")[1]);
  var prevI = parseInt(arr[i-1].toLowerCase().split("s")[1]);
  if (thisI != prevI+1) {
    while(thisI-1 !== prevI++){
       console.log(`Seems like ${prevI} is missing. thisI is ${thisI} and prevI is ${prevI}`)
    }
   }
}

However, I feel like I'm overly complicating things. I thought of creating an ideal array:

var idealArray = [];
for (var i =0; i<200;i++) {
  idealArray.push(i)
}

And then, while checking, tamper with my array (arr) so that the loop checks two arrays of the same length. I.e., use this solution:

var idealArray = [];
for (var i =0; i<200;i++) {
  idealArray.push(i)
}
var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];
for (let i = 0; i<idealArray.length;i++){
  if (parseInt(arr[i].toLowerCase().split("s")[1]) != idealArray[i]) {
    console.log(`Seems like ${idealArray[i]}is missing`);
    arr.splice(i,0,"dummyel")
  }
}

But, once again, I have the feeling that creating this second array is not very efficient either (thinking of a big list, I'd waste unnecessary space).

So... how do I efficiently perform this task in JavaScript? (Efficiently meaning as close to O(1) as possible both for time complexity and for space complexity.)

Answer 1

Here is the recursive approach based on accepted answer but refactored to return the data:

var arr = ["s00", "s01", "s02", "s03", "s04", "s05", "s07", "s08", "s09", "s10", "s11", "s12", "s13", "s14", "s17", "s19", "s20", "s21", "s22", "s24", "s25", "s26", "s27", "s28", "s30", "s32", "s33", "s34", "s36", "s38", "s39", "s41", "s43", "s44", "s45", "s46", "s47", "s48", "s49", "s50", "s51", "s52", "s53", "s54", "s55", "s56", "s58", "s60", "s61", "s62", "s63", "s64", "s65", "s67", "s69", "s70"];

function findMissing(arr, l, r) {
  var lval = Number(arr[l].substr(1));
  var rval = Number(arr[r].substr(1));
  // the segment has no gaps
  if (r - l === rval - lval) {
    return [];
  }
  // the segment has exactly two items
  if (r - l === 1) {
    return Array.from({ length: rval - lval - 1 }, function(x, i) {
      return "s" + (lval + 1 + i);
    });
  }
  // calculate middle using integer cast trick
  var m = (l + r) / 2 | 0;
  // process the segments [l, m] and [m, r]
  // note that m is processed twice and requires extra recursion
  // however this eliminates the extra coding needed to handle
  // the case where m and m + 1 are not consecutive
  return findMissing(arr, l, m).concat(findMissing(arr, m, r));
}
var result = findMissing(arr, 0, arr.length - 1);
console.log(result);

Answer 2

Using an array of Booleans to keep track of items present:-

let numbers = arr.map(s => +s.slice(1)); // Convert to numbers
let maximum = Math.max.apply(null, numbers); // Get the maximum
let missing = Array(maximum).fill(true); // start with all missing
let answer = numbers.reduce((p, c) => (p[c] = false, p), missing); // set to false if there
answer.forEach((e,i) =>  (e && console.log(i + " seems to be missing"))); // show answer

Also works for randomly arranged numbers.

Answer 3

A quick and simple solution is to join all elements of an array into a string and then search inside that string.

Here is a solution that takes an array (ordered or unordered, works fine in any case) with any pattern (no hard-coded s0x pattern needed):

    const arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];
    let firstIndex = Number(arr[0].replace(/\D/, ''));
    let lastIndex = Number(arr[arr.length-1].replace(/\D/, ''));
    let separator = ',';
    
    let arrString = separator + arr.join(separator) + separator;
    for (let i = firstIndex; i <= lastIndex; i++) {
    	let element = arr[0].slice(0, arr[0].length - String(i).length) + i;
    
    	if (arrString.indexOf(separator + element + separator) < 0) {
			console.log(element)
    	}
    }

Answer 4

Javascript version of the C program above, one that allows for sequences of missing elements.

var util = require( 'util' );

//  Array of data.
var arr = [
        1,  2,  3,  4,  5,  6,  7,  8,  9,
    10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
    20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
    30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
    40, 41, 42, 43,         46, 47, 48, 49,
    50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
    60, 61, 62, 63, 64, 65, 66, 67, 68, 70
];
var arr_len = arr.length;

//  Empty array?
if (arr_len == 0)
{
    console.log(
        util.format(
            "No elements." ));
    process.exit( 0 );
}

//  Pre-check.
var lim = arr[arr_len - 1] - (arr_len - 1);
if (lim == 0)
{
    printf(
        "No missing elements.\n" );
    return 0;
}

//  Initialize binary search.
var lo  = 0;
var hi  = arr_len;
var mid = 0;

//  Search metadata.
var cnt = 0;
var prv = 0;
var val = 0;
var i;

for (i = 0; i < arr_len && cnt < lim; i++)
{
    //  Get mid point of search.
    mid = (lo + hi) >> 1;

    //  Get array value, adjust and do comparisons
    val = arr[ mid ] - cnt;
    if (val === mid)
        lo = mid + 1;
    if (val > mid)
        hi = mid - 1;

    //  Have we found something?
    if (lo > hi)
    {
        //  Yes.  Divide and conquer.
        hi  = arr_len;
        prv = cnt;
        cnt = arr[ lo ] - lo;

        //  Report missing element(s).
        console.log(
            util.format(
                "Missing %d elements @ arr[ %d ] == %d, probes = %d",
                cnt - prv,
                lo,
                arr[ lo ],
                i + 1 ));
    }
}

console.log(
    util.format(
        "Probes: %d",
        i ));

Answer 5

So, if you know there are no duplicates and that the entries are in order, a fairly simple process would be to start by checking the number of elements in the list.

The length of arr should be equal to the number of consecutive elements, yes?

*** Caveat: If the elements are not sorted or there could be duplicates, this won't work, of course.

Assuming the conditions apply then a simple binary search would find the first missing element.

After that, it is a divide and conquer, with the binary search being limited to the upper part of the search space in order to find the next missing element. A recursive algorithm would be easy to understand, but you could also do it in a single function.

Note that the elements contain a relationship between their list indices. In your binary search, if "s08" is in element seven, then you know there is a missing element earlier in the array.

The binary search is fairly easy, and would probably benefit from a less naive way of comparison as well, since the elements are a fixed field string.

The adjustment for missing elements is fairly easy, as well. Each missing element shifts the rest of the elements one index left, so that turns into a simple integer operation.

Seriously? It isn't that hard:

#include    <stdio.h>
#include    <stdlib.h>

#define ARY_SZ  68

static
int arr[ARY_SZ] =
{
        1,  2,  3,  4,  5,  6,  7,  8,  9,
    10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
    20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
    30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
    40, 41, 42, 43,     45, 46, 47, 48, 49,
    50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
    60, 61, 62, 63, 64, 65, 66, 67, 68, 70
};

int
main(
    void )
{
    int     i,
            lim,
            lo,
            hi,
            mid,
            val,
            cnt;

    /*  Pre-check.  */
    lim = arr[ARY_SZ - 1] - (ARY_SZ - 1);
    if (lim == 0)
    {
        /*  No missing elements.    */
        printf(
            "No missing elements.\n" );
        return 0;
    }

    /*  Initialize binary search.   */
    lo  = 0;
    hi  = ARY_SZ;
    cnt = 0;

    /*  For (at most) the number of array elements, do: */
    for (i = 0; i < ARY_SZ && cnt < lim; i++)
    {
        /*  Get mid point of search.    */
        mid = lo + hi >> 1;

        /*  Get array value, adjust and do comparisons. */
        val = arr[ mid ] - cnt;
        if (val == mid)
            lo = mid + 1;
        if (val > mid)
            hi = mid - 1;

        if (lo > hi)
        {
            /*  Report missing element. */
            printf(
                "Missing element @ arr[ %d ] == %d, probes = %d\n",
                lo,
                arr[ lo ],
                i );

            /*  Divide and conquer. */
            hi   = ARY_SZ;
            cnt += 1;
        }
    }

    printf(
        "Probes = %d\n",
        i - 1);

    return 0;
}

The results of compiling this C code and running it:

Missing element @ arr[ 0 ] == 1, probes = 5
Missing element @ arr[ 43 ] == 45, probes = 11
Missing element @ arr[ 67 ] == 70, probes = 16
Probes = 16

So, no linear search necessary, and a maximum of 16 probes required to find the three missing elements.

Answer 6

This version fills an array with all possible values and then picks the ones missing:

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];

var fullArray = Array(71).fill().map((item, index) => "s"+(""+(0 + index)).padStart(2,"0"));

var missingValues = fullArray.filter( ( el ) => !arr.includes( el ) );

console.log(missingValues);

With a bit more of readability and reusability:

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];

var prependString = "s";
var numberOfDigits = 2;
var initialNumber = 0;
var finalNumber = 70;

var fullArray = Array(finalNumber - initialNumber + 1)
    .fill()
    .map((item, index) => prependString+(""+(initialNumber + index)).padStart(numberOfDigits,"0"));

var missingValues = fullArray.filter( ( el ) => !arr.includes( el ) );

console.log(missingValues);

Answer 7

As I understand from your ideal array solution, you know the maximum array size(?). So if you have 100 maximum values and expect S00 - S99 you can do:

var arrayIndex=0;
for (var i =0; i<100;i++) {
   var idealValue="s"+("00"+i).slice(-2); // To get S01-S99
   if(arr.length <= arrayIndex || arr[arrayIndex]!=idealValue){
        console.log(idealValue + 'is missing');
   }
   arrayIndex++;
}

Or something like that. I can't test it right now ;) But iterate through the list of ideal values and compare the same value in the array. If it doesn't match print it.

Answer 8

You could reduce the array by taking two elements of the array and fill the gaps, if exists.

const
    getNumber = s => +s.slice(1),
    pad = i => ('00' + i).slice(-2);

var array = ["s00", "s01", "s02", "s03", "s04", "s05", "s07", "s08", "s09", "s10", "s11", "s12", "s13", "s14", "s17", "s19", "s20", "s21", "s22", "s24", "s25", "s26", "s27", "s28", "s30", "s32", "s33", "s34", "s36", "s38", "s39", "s41", "s43", "s44", "s45", "s46", "s47", "s48", "s49", "s50", "s51", "s52", "s53", "s54", "s55", "s56", "s58", "s60", "s61", "s62", "s63", "s64", "s65", "s67", "s69", "s70"],
    result = [];

array.reduce((left, right) => {
    var l = getNumber(left),
        r = getNumber(right);

    while (++l < r) {
        result.push('s' + pad(l));
    }
    return right;
});

console.log(result);

Answer 9

Your solution with the inner while-loop seems already quite good, just omit the unnecessary if, and keep track of the number that you are currently expecting to see instead of parsing the previous number every time.

Something like this:

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];
var expectedI = 0
for (var i = 0; i < arr.length; i++) {
  var currentI = parseInt(arr[i].toLowerCase().split("s")[1]);
  while (expectedI < currentI) {
    console.log(`Seems like ${expectedI} is missing.`)
    expectedI++
  }
  expectedI = currentI + 1
}

gives you:

Seems like 6 is missing.
Seems like 15 is missing.
Seems like 16 is missing.
Seems like 18 is missing.
Seems like 23 is missing.
Seems like 29 is missing.
Seems like 31 is missing.
Seems like 35 is missing.
Seems like 37 is missing.
Seems like 40 is missing.
Seems like 42 is missing.
Seems like 57 is missing.
Seems like 59 is missing.
Seems like 66 is missing.
Seems like 68 is missing.

The idea is very simple: if you don't see the number that you expected to see, print it to console (or save it elsewhere), then continue with the next number.

Note that you can't get the runtime below O(N), because you have to look at every element of the list at least once, and it could also happen that you have to print O(N) missing elements to the console.

The above algorithm looks at every element of the list once, and can function with constant space overhead.

EDIT: The comment made by vlaz seems to propose an algorithm that should work faster for arrays with few gaps. However, this still does not change the worst case behavior, because in the worst case (if everything is missing), you still have to print all N numbers. If you assume that the number k of missing numbers is "much smaller" than N (i.e. k not in Theta(N)), then more efficient algorithms could be possible.

Answer 10

Since you know you are expecting a sequential array, I don't know why it needs to be more complicated than a loop through numbers arr[0] through arr[end] while keeping a counter to know where you are in the array. This will run at O(n), but I don't think you can improve on that — you need to look at every element at least once in the worst case.

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];

let first = parseInt(arr[0].substring(1))
let last =  parseInt(arr[arr.length-1].substring(1))
let count = 0
for (let i = first; i< last; i++) {
   if (parseInt(arr[count].substring(1)) == i) {count++; continue}
   else console.log(`seem to be missing ${'s'+i.toString().padStart(2,'0')} between: ${arr[count-1]} and ${arr[count]}` )
}

---

EDIT:

After thinking a bit about the comments below, I made a recursive approach that splits the array and checks each half. Mostly as an experiment, not as a practical solution. This does in fact run with fewer than n iterations in most cases, but I couldn't find a case where it was actually faster Also, I just pushed indexes showing where the gaps are to make the structure easier to see and test. And as you'll see, because it's recursive the results aren't in order.

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];

let missingGaps = []

function missing(arr, low, high) {
  if (high <= low) return

  let l = parseInt(arr[low].substring(1))
  let h = parseInt(arr[high].substring(1))

  if (h - l == high - low) return
  if (high - low === 1) {
    missingGaps.push([low, high])
    return
  } else {
    let mid = ((high - low) >> 1) + low
    
    missing(arr, low, mid)

    // need to check case where split might contain gap
    let m = parseInt(arr[mid].substring(1))
    let m1 = parseInt(arr[mid + 1].substring(1))
    if (m1 - m !== 1) missingGaps.push([mid, mid + 1])

    missing(arr, mid + 1, high)
  }
}

missing(arr, 0, arr.length-1)
missingGaps.forEach(g => console.log(`missing between indices ${arr[g[0]]} and ${arr[g[1]]}`))

Maybe another answer or comment will have an improvement that makes it a bit faster.

Answer 11

This is just an approach to find if, in given array, some element in a number sequence is missing. We could use (n*(n+1))/2 that resolve addition on n first numbers. Also, If the array starts with for example 10 we remove 1-10 sum. This just telling us if something is missing, but not what is missing. The advantage is that the array could be unsorted. Calculate minimum is less expensive than order the entire array.

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];

let total = 0;

for(let i = 0; i<arr.length; i++){
    arr[i] = parseInt(arr[i].replace("s", ""));
    total += arr[i];
}

let hipFirstSum = ((arr[0]-1)*(arr[0]))/2;  //or minimun
let n = arr[arr.length -1];
let hipSum = (n*(n+1))/2;
let realSum = hipSum - hipFirstSum;

(realSum != total)?console.log("wrong"):console.log("good");

Answer 12

You can go for something like this that compares each array item to the one next to it then if the difference is greater than 1 display all the numbers in between can be logged.

const arr = ["s00", "s01", "s02", "s03", "s04", "s05", "s07", "s08", "s09", "s10", "s11", "s12", "s13", "s14", "s17", "s19", "s20", "s21", "s22", "s24", "s25", "s26", "s27", "s28", "s30", "s32", "s33", "s34", "s36", "s38", "s39", "s41", "s43", "s44", "s45", "s46", "s47", "s48", "s49", "s50", "s51", "s52", "s53", "s54", "s55", "s56", "s58", "s60", "s61", "s62", "s63", "s64", "s65", "s67", "s69", "s70"];

for (let i = 0; i < arr.length - 1; i++) {
  let currentNum = parseInt(arr[i].split("s")[1]);
  let difference = parseInt(arr[i + 1].split("s")[1]) - currentNum;
  if (difference === 1) continue

  for (let d = 1; d < difference; d++)
    console.log(`Seems likes ${currentNum+d} is missing`)
}

I hope you find this helpful.