Skip to content

Instantly share code, notes, and snippets.

@agar3s
Last active April 14, 2021 18:50
Show Gist options
  • Save agar3s/6ed825080e4070e933c90f8ad7727e6a to your computer and use it in GitHub Desktop.
Save agar3s/6ed825080e4070e933c90f8ad7727e6a to your computer and use it in GitHub Desktop.
/*
* 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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment