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.
solution([-1,-2])
will throw an error.
solution([1,2e100])
will throw an error.
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*/}