function findSmallestPositiveInteger(A) {
// sort array from smallest to largest number
A.sort((a, b) => a - b)
// remove duplicates because they just would take memory
const noDups =Array.from(new Set(A).keys())
let smallestPositiveInteger=1
let previous = noDups[0]
if(previous <= smallestPositiveInteger && previous>0)
smallestPositiveInteger++
for(let i =1;i<noDups.length;i++){
const v = noDups[i]
if(previous > 0){
const diffWithPrevious = v - previous
// the logic for this early return is that we might not need to traverse
// the whole array for example imagine this example
// [1,2,5,6,8,...n]
// its clear that there is a gap between 5 and 2 so we can just
// conclude that 2+1 is the smallest postive integer not in our array
if(diffWithPrevious > 1) return previous +1;
}
// check if smallest positive integer in array is not 1
// if so return 1
if(previous == 0 && v > 1 ) return 1
if(v <= smallestPositiveInteger && v>0)
smallestPositiveInteger++
previous = v
}
return smallestPositiveInteger
}
const arr =[-1,-2,1,3,10,9,3,2,3,3,10,2,7,99,100,10000,500,50,60,70,33]
console.log(findSmallestPositiveInteger(arr))
Put the integers from the array into a lookup structure, and then just try natural numbers starting from 1 until you find one that was not in the array:
function findSmallestPositiveInteger(arr) {
const lookup = new Set(arr);
let i = 1;
while (lookup.has(i)) {
i++;
}
return i;
}
You could remove the sorting and build out an object where the keys are the values in the array. Then just iterate over the arrays length and break at the first missing number.
function findSmallestPositiveInteger(A) {
const noDups = Object.assign({} , ...A.map((x) => ({[x]: true})));
let smallestPositiveInteger = 1
for (let i = 1; i < A.length; i++) {
if (typeof noDups[i] == 'undefined') {
smallestPositiveInteger = i;
break;
}
}
return smallestPositiveInteger;
}
const arr = [-1, -2, 1, 3, 10, 9, 3, 2, 3, 3, 10, 2, 7, 99, 100, 10000, 500, 50, 60, 70, 33]
console.log(findSmallestPositiveInteger(arr))
I guess I'd go about it in the following manner.
A little something like this I supppose.
"use strict";
window.addEventListener('load', onLoad, false);
function onLoad(evt)
{
let arr =[-1,-2,1,3,10,9,3,2,3,3,10,2,7,99,100,10000,500,50,60,70,33];
test(arr);
}
function test(arr)
{
arr = arr.sort(function(a, b){return a-b});
let nextTgt = 1;
arr.forEach( el => { if (el==nextTgt) nextTgt++ ;} );
console.log(arr);
console.log(nextTgt);
}EDIT: A vast improvement would break from the loop if the current array element being examined is larger than the current search target.
function test2(arr)
{
arr = arr.sort(function(a, b){return a-b});
let nextTgt = 1;
for (var i=0,n=arr.length; i<n; i++)
{
if (arr[i] == nextTgt)
nextTgt++;
else if (arr[i]>nextTgt)
break;
}
console.log(arr);
console.log(nextTgt);
}