Get the first positive value that does not exist in array

Question

function solution(A) {
    var len = A.length;
    if(len > 1){
        let max = Math.max.apply(null, A);
        let range = Array.from(Array(max).keys());
        for(let i = 0; i < range.length; i++){
            if(A.includes(range[i]) === false){
                if(range[i] > 0){
                    return range[i];
                }
                continue;
            }
            continue;
        }
        return max + 1;
    }else if(len == 1 && (A[0] < 1 || A[0] > 1)){
        return 1;
    }else if((len == 1) && (A[0] == 1)){
        return 2;
    }
    return 1;
}

This is mainly used to get the first positive value that does not exist in sequence of integers in an array.

There is a time complexity of O(N ** 2).

Can it be better than this?

If there is no better complexity, can we optimize the for loop better than that?

Answer 1

Review

There are 3 answers already, yet none have addressed the flaws or reviewed your code.

Thus I will give a detailed review and an alternative solution

Your solution has bugs that make a estimation of complexity impossible.

To help review your code I have numbered the lines. See Snippet (B) for line numbers

Flaws AKA bugs

There are many cases where your code can not run. 3 different errors the last is the worst type of error uncatchable.

1. solution([-1,-2]) will throw an error.
2. solution([1,2e100]) will throw an error.
3. solution([1,2**31]) will crash the page after a long hangup on all but the top end machines.

Your code is not \$\mathcal{O}(n^2)\$ but rather it is incomplete or if run on a perfect machine \$\mathcal{O}(\infty)\$ (and same storage) as that is the largest number that the function Math.max can return.

Or if you have a max value less than the array size max then the complexity is \$\mathcal{O}(2^{m+1})\$ where \$m\$ is the max value in the array.Thus the complexity for input [1,2**32-1] is a whopping \$\mathcal{O}(n^{33})\$ and storage of \$\mathcal{O}(n^{32})\$

By the lines

The following numbered items (bold numbers 1) refer to your source code by line number

• 1 A is a very poor name, arr, array, nums, numbers or many more. Even a would be better as we do not capitalize variable names unless they are instantiatable objects defined as functions or using the class syntax.
• 2 len should be a constant. eg const len as it is not to be reassigned at any point in the code.
• 3, 16 and 17. The if statements can be rearranged to reduce complexity.
• 4 max should be a constant. Its almost 2019 and the spread operator ... has been available for 4 years, Use it!!! Line 4 becomes const max = Math.max(...A);
• 5 Use constant const range =. You create an array of indexes from 0 to max. Which is a major problem, (See intro above) The irony is that you can (and do) calculate all the values from 0 to max via the for loop on the next line making line 7. A.include(range[i]) is identical to A.include(i)
• 6 range.length is the same as max so use the shorter form for (let i = 0; i < max; i ++) {
• 7 Use the shorter form for not true if (! A.includes(range[i])) {
• 8 Use the shorter form is truthy. All numbers !== 0 are truthy true thus this line can be if (range[i]) {
• 9 Could be return i;
• 11 and line 13 the continue is not needed as you are at the bottom of the for loop at those lines already.
• 16 Use the strict equality operator len === 1. use the shorter not form of val < value || val > value as val !== value, making the line } else if (len === 1 && A[0] !== 1) {
• 18 Use the strict equality operators, There is no need for the () around each clause } else if (len === 1 && A[0] === 1) {

General points.

• If you return inside a statement block, you should not include the else at the end as It will never be used. Thus lines 16 and 17 do not need the else and can be moved down one line (away from the closing })

• Though not a must it is cleaner to put spaces after for, if, else etc, before else, between ){

• When you find you are needing to search a set of values repeatedly it pays to consider using a Map or Set to find the matches as they use a hash to lookup values and have a complexity of \$\mathcal{O}(1)\$ for the search, however to create the lookups is \$\mathcal{O}(n)\$. Thus using a Map or Set you can easily reduce complexity from \$\mathcal{O}(n^2)\$ to \$\mathcal{O}(n)\$. There is a storage penalty meaning you can go from \$\mathcal{O}(1)\$ to \$\mathcal{O}(n)\$.

Rewriting you code

Using a Set to remove the \$\mathcal{O}(n)\$ overhead of each Array.includes

The Set positiveInts can be created as we iterate the array, saving a little complexity.

I assume array items are less than or equal to Number.MAX_SAFE_INTEGER

Snippet (A)

function solution(array) {
    var min = 1;
    if (array.length === 1) {
        min = array[0] === 1 ? 2 : min;
    } else if (array.length) {
        const positiveInts = new Set();
        for (const val of array) {
            if (val > 0) {
                positiveInts.add(val);
                if (val === min) {                        
                    while (positiveInts.has(min)) { min ++ }
                }
            }
        }
    }
    return min;
}

Snippet (B)

/*lines*/
/* 1*/function solution(A) {
/* 2*/    var len = A.length;
/* 3*/    if(len > 1){
/* 4*/        let max = Math.max.apply(null, A);
/* 5*/        let range = Array.from(Array(max).keys());
/* 6*/        for(let i = 0; i < range.length; i++){
/* 7*/            if(A.includes(range[i]) === false){
/* 8*/                if(range[i] > 0){
/* 9*/                    return range[i];
/*10*/                }
/*11*/                continue;
/*12*/            }
/*13*/            continue;
/*14*/        }
/*15*/        return max + 1;
/*16*/    }else if(len == 1 && (A[0] < 1 || A[0] > 1)){
/*17*/        return 1;
/*18*/    }else if((len == 1) && (A[0] == 1)){
/*19*/        return 2;
/*20*/    }
/*21*/    return 1;
/*22*/}

Answer 2

If there is no better complexity than N**2, can we optimize the for loop better than that?

Complexity is more subtle: your code is O(N²) in the worst case (A is an arithmetic progression with an initial term of 1 and a common difference of 1: [1,2, ... , N]) but O(N) in the best case (A doesn't contain 1).

If you chose to sort the array A first, which is a O(n*log(n)) operation, then searching for the first non-negative, non-consecutive pair of elements would be a O(n) operation. It means the solution is reliably O(n*log(n)): it's better than your worst case, but worse than your best case. So which one is better? It's up to you to decide. It depends a lot on what you know about your input. If there are a lot of negative values, for instance, you could remove them as the first step: a partition is a O(n) operation.

Now, if we leave the realm of the big O notation, creating an array of max(A) size can be a very costly operation. What if Math.max.apply(null, A); returns 99999999999999999999999999? Imagine an array this size, and then having to populate it with increasing values? So @Victor's proposed solution is better than your original code.

Answer 3

How about just brute forcing it?

function solution(A) {
    for (let n = 1;; n++) {
        if (A.indexOf(n) === -1) {
            return n;
        }
    }
}

UPD: The bottleneck of the above function is the indexOf method that should search entire array for the passed number. You have to pass large arrays, to significantly increase the speed you may want to convert array to object by swapping values and indices. This would be faster because checking whether an object has a property is much faster than searching for a value in an array.

function solution(A) {
    let obj = {};
    for (let i of A) {
        if (i > 0) {
            obj[i] = 1;
        }
    }

    for (let n = 1; ; n++) {
        if (!(n in obj)) {
            return n;
        }
    }
}

Answer 4

I think we have being make in 2 stages.

FIRST sorting array;

const arr = [-5, 44, 43, -3, -7, 3, 3, 1, 2,  7, 4];
 arr.sort((item1, item2) => item1 - item2);
 console.log(arr);

SECOND. Array is sorting it means that every element of array will be equal array position minus positive position. However, we can have duplicate fields and we must process this situation:

//const arr = [-5, 44, 43, -3, -7, 1, 2,2,3, 5];
//const arr = [ 0, 1, 0, 1, 0, 1,  2,  7, 4];
const arr = [ -100, -200];
 arr.sort((item1, item2) => item1 - item2);
 console.log(arr);
 
 // SECOND part
     
 let position = 0;
 let index = 1;
 for(let i = 0; i < arr.length; i++) {
      
     if(arr[i] <= 0) { //if NOT positive value we add one to position
       position = position + 1;
       continue;
     }
     
     if(i > 0 && arr[i] === arr[i-1]) {//if NOT duplicate value 
       position = position + 1;
       continue;
     }
     
     index = i - position + 1;
     if(arr[i] !== index) {// end if value != index
       break;
     }
 }
 
 console.log(index);

As result we have Sorting and one loop.