Question

0

204

Views

how can you improve this algorithm for finding the smallest positive integer not in an array


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

8 months ago · Santiago Gelvez

3 answers

Answer question

0

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

8 months ago · Santiago Gelvez Report

0

I guess I'd go about it in the following manner.

sort the array, treating each element as a number (arr.sort treats as a strnig without a compare function)
set a target variable to 1
stepping through the elements, if my target is found, increment the number we now look for
when finished looping, return the value that we were last searching for

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

8 months ago · Santiago Gelvez Report

Answer question

Find remote jobs

Accepted Answer · 2022-06-24T19:59:51.055Z

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