solution.js

/*
* Write a function:
* 
* function solution(A);
* 
* that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
* 
* For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
* 
* Given A = [1, 2, 3], the function should return 4.
* 
* Given A = [−1, −3], the function should return 1.
* 
* Write an efficient algorithm for the following assumptions:
* 
* N is an integer within the range [1..100,000];
* each element of array A is an integer within the range [−1,000,000..1,000,000].
*/

let space = [[0, 0], [1000000, 1000000]];
function solution (array) {
  space = [[0, 0], [1000000, 1000000]];
  for (let index = 0; index < array.length; index++) {
    const element = array[index];
    // find the position into the space 
    binaryUpdate(element);
    console.log(space);
  }
  return space[0][1] + 1;
}

function binaryUpdate (element) {
  if (element < 1 || element > 1000000) return;

  let maxIndex = space.length - 1;
  let minIndex = 0;
  
  let updated = false;
  while(!updated) {
    let index = minIndex + (~~((maxIndex - minIndex) / 2));

    let leftBucket = space[index];
    let rightBucket = space[index + 1];
    if (element > leftBucket[1] && element < rightBucket[0]) {
      if (element === leftBucket[1] + 1) {
        leftBucket[1] = element;
        updated = true;
      }
      if (element === rightBucket[0] - 1) {
        rightBucket[0] = element;
        updated = true;
      }
      if (rightBucket[0] - leftBucket[1] < 2) {
        // should merge this buckets
        leftBucket[1] = rightBucket[1];
        space.splice(index + 1, 1);
        updated = true;
      }
      
      // insert a new item in between if number are not consecutive
      if (!updated) {
        space.splice(index + 1, 0, [element, element]);
        updated = true;
      }
    } else if( element >= leftBucket[0] && element <= leftBucket[1]) {
      // is inside left bucket - do nothing
      updated = true;
    } else if( element >= rightBucket[0] && element <= rightBucket[1]) {
      // is inside right bucket - do nothing
      updated = true;
    } else if ( element < leftBucket[0] ) {
      maxIndex = index;
    } else if ( element > rightBucket[1] ) {
      minIndex = index;
    }
  }

}

function test(array, value) {
  console.log(array, value, solution(array) === value);
}

test([1, 3, 6, 4, 1, 2], 5);
test([1, 2, 3], 4);
test([-1, -3], 1);