Given an array of integers, return the smallest positive integer not in it Write a function:

function solution(A);

  
  that, given an array A of N integers, returns the smallest positive
  integer (greater than 0) that does not occur in A.
  
  For example, given A = [1, 3, 6, 4, 1, 2], the function should return
  5.
  
  Given A = [1, 2, 3], the function should return 4.
  
  Given A = [−1, −3], the function should return 1.
  
  Assume that:
  
  
  N is an integer within the range [1..100,000]
  Each element of array A is an integer within the range [−1,000,000..1,000,000]
  
  
  Complexity:
  
  
  Expected worst-case time complexity is \$O(N)\$
  Expected worst-case space complexity is \$O(N)\$, beyond input storage (not counting the storage required for input arguments)
  
  
  Elements of input arrays can be modified.


Solution in \$O(n^2)\$:

function solution(A) {
  for (i = 1; i &lt; 1000000; i++) {
    if(!A.includes(i)) return i;
  }
}
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

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 &lt; nums.length; i++) {
        while (0 &lt; nums[i] &amp;&amp; nums[i] - 1 &lt; nums.length
                &amp;&amp; nums[i] != i + 1
                &amp;&amp; nums[i] != nums[nums[i] - 1]) {
            swap(i, nums[i] - 1);
        }
    }

    for (let i = 0; i &lt; 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.