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

  • A+
Category:Languages

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 2nd array is not very efficient either (thinking of a big list, I'd waste unnecessary space).

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

P.S. I searched for duplicates and didn't find one. And it also seems to be on-topic, nonetheless I'd appreciate any constructive feedback in this direction as well


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

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: