How do you look through arrays more efficiently? Javascript

Question

I've been doing a lot of the practise tests on codility and though all my solutions work, they always have hidden stress tests which include massive arrays, the following code for example needs to take array A and find the lowest positive number missing from the sequence.

e.g: given A = [1, 3, 6, 4, 1, 2], the function should return 5. 5 is the value of i which increments in the loop. Function returns whenever index i is not found in array.

It works correctly but codility tested it with a 1-100,000 array and it timed out at the 6 second limit. most of my codes on the practise tests tend to fail for the same reason. Any help greatly appreciated.

console.log(solution([1, 3, 6, 4, 1, 2]));
function solution(A) {
    let i = 0
    for (i = 1; i <= A.length ; i++){
        if(A.includes(i) == false){
            return i
        }
    }
    return i
}

Answer 1

There is no way to look through N items in less than O(n) which is what you're doing. The issue is you're looking through the array N times as well - this means you run N*N times and can be improved.

The most "typical" way to improve this approach is to use a Set or similar data structure with amortised (usually) constant-time access to elements. In your case this would look like:

console.log(solution([1, 3, 6, 4, 1, 2]))
function solution(A) {
    // build existing elements, in O(N)
    const values = new Set(A)
    let i = 0
    for (i = 1; i <= A.length; i++){
        if(!values.has(i)){
            return i
        }
    }
    return i
}

This runs in O(N) (creating the set) + O(N) iterating the array and performing constant time work each time.

Answer 2

Your code loops through every item in the array for every item in the array. This gives a worst-case runtime of O(n^2). You can get a much better result if you sort the array, and then iterate through it looking for any missing numbers.

function compareNumeric(a,b) {
    return a - b;
}

function solution(A) {
    A.sort(compareNumeric);
    let expect = 0;
    for( let i=0; i<A.length; i++) {
        if( A[i] > expect+1) return expect+1;
        if( A[i] === expect+1) expect++;
    }
    return expect+1;
}

console.time('simple');
console.log(solution([1, 3, 6, 4, 1, 2]));
console.timeEnd('simple');

// worst-case: all numbers from 1-1M exist but are randomly shuffled in the array
const bigArray = Array.from({length:1000000},(_,i)=>i+1);
function shuffle(a) {
    // credit: https://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]];
    }
    return a;
}
shuffle(bigArray);
console.time('worst-case');
console.log(solution(bigArray));
console.timeEnd('worst-case');

This will give you a runtime of O(n log n) and should be the fastest possible solution as far as I can tell.

Answer 3

Please check the two solutions, it will take the time complexity O(n * log n) or O(n) so it will be much faster than previous work.

const arrayGenerator = (len) => {
  const array = [];
  for(let i = 0; i < len; i ++) {
    array.push(Math.floor(Math.random() * len) + 1);  
  }
  return array;
}

function sort_array_solution(A) {    
    A.map(a=>a).sort((a, b)=>a - b)    
    let ans = 1;
    for(let i = 0; i < A.length; i ++) {
      if(A[i] < ans) continue;
      if(A[i] > ans) return ans;
      ans ++;
    }
    return ans;
}

function object_key_solution(A) {    
    const obj = {}
    
    for(let i = 0; i < A.length; i ++) {
      obj[A[i]] = 1;
    }        
    
    for(let ans = 1; ; ans ++) {
      if(!obj.hasOwnProperty(ans)) return ans;      
      ans ++;
    }    
    return ans;
}


console.log(sort_array_solution([1,2]))
console.log(object_key_solution([1,2]))

const arr = arrayGenerator(10);
console.log(sort_array_solution(arr))
console.log(object_key_solution(arr))

const arr1 = arrayGenerator(100000);
console.log(sort_array_solution(arr1))
console.log(object_key_solution(arr1))