That’s a nice simple solution, with two problems:

- It will give incorrect result when
`A`

contains all the values in the ranges`[1..1000000]`

or`[1..999999]`

, returning`undefined`

instead of 1000001 and 1000000, respectively. - It doesn’t meet the time complexity requirement, being $O(n^2)$ instead of $O(n)$.

The first problem is easy to fix by adjusting the end condition of the loop.

The second problem is trickier, and the interesting part of the exercise.

Consider this algorithm, that’s $O(n)$ in time and $O(1)$ in space:

- Loop over the elements of
`A`

from the start, and for each value`A[i]`

, if`A[i] - 1`

is a valid index in the array, then repeatedly swap`A[i]`

and`A[A[i] - 1]`

until`A[i]`

is in its correct place (value equal to`i + 1`

), or`A[i]`

and`A[A[i] - 1]`

are equal.- This should order the values to their right places such that
`A[i] == i + 1`

, when possible

- This should order the values to their right places such that
- Loop over the elements again to find an index where
`A[i] != i + 1`

, if exists then the missing value is`i + 1`

- If the end of the loop is reached without returning a value, then the missing value is
`A.length + 1`

.

Here’s one way to implement this in JavaScript:

```
var firstMissingPositive = function(nums) {
var swap = function(i, j) {
var tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
};
for (let i = 0; i < nums.length; i++) {
while (0 < nums[i] && nums[i] - 1 < nums.length
&& nums[i] != i + 1
&& nums[i] != nums[nums[i] - 1]) {
swap(i, nums[i] - 1);
}
}
for (let i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return nums.length + 1;
};
```

Note: to verify this, or alternative implementations work,

you could submit on leetcode.

How about this solution, which – if I’m not mistaken – should fulfill all requirements:

- create a second array
- run through all elements of the input array
- for each number set the respective key in the second array to true
- run through the second array and return the first key which value comes back as
`undefined`

- if no match is found, return
`1`

, so it will work for an empty input array as well

```
function findNumber(values) {
let result = [];
for (let i = 0; i < values.length; ++i) {
if (0 <= values[i]) {
result[values[i]] = true;
}
}
for (let i = 1; i <= result.length; ++i) {
if (undefined === result[i]) {
return i;
}
}
return 1
}
```

Try it yourself

^{Patrick and I had a discussion about the real time performance of our solutions (Here’s Patrick’s elegant solution using Set). We set up a test, containing around 1000 elements in the input array, including lots of negative values. You can try the test yourself.
}

^{
JollyJoker suggested a similar version in the comments using JavaScript’s built-ins filter, reduce and findIndex. I fixed the suggested solution for edge cases and added it to the performance test. You can now test all three solutions. Keep in mind that these built-ins come with some overhead.
}

^{
Janos added code for his algorithm as well now. To complete the performance test, I’ve added it as well and here’s the final fiddle containing all four solutions.
}

In order to satisfy the *O(N)* time-complexity, construct a `Set()`

in *O(N)* time and space complexity, then use a `while`

loop which is considered ~~constant time relative to ~~ *N*** O(N) as well** (thank you, wchargin), since the maximum possible number of iterations is equal to

*N*and average performance of a

`Set#has()`

operation is *O(1)*. Because

*O(N + N) = O(N)*, regarding time complexity, this solution is overall

*O(N)*performance in both time and space:

```
function solution(A) {
const set = new Set(A);
let i = 1;
while (set.has(i)) {
i++;
}
return i;
}
```

^{While this is a relatively simplistic and deceivingly elegant implementation, insertusernamehere’s solution is admittedly an order of magnitude faster, when using an array as a perfect hash table for non-negative integers instead.}