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

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.