Smallest positive integer not in array JavaScript | Example code

How to Find the smallest positive integer, not in given an array of numbers?

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.

Example and Algorithm Smallest positive integer not in array JavaScript

HTML example code.

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:

<!DOCTYPE html>
<html>
<body>

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

  var A = [1, 3, 6, 4, 1, 2];
  console.log(firstMissingPositive(A));  

</script>

</body>
</html>

Source: codereview.stackexchange.com

Output:

Smallest positive integer not in array JavaScript

The solution in O(n2):

<!DOCTYPE html>
<html>
<body>

  <script>
    function solution(A) {
      for (i = 1; i < 1000000; i++) {
        if(!A.includes(i)) return i;
      }
    }

    var A = [1, 3, 6, 4, 1, 2];
    console.log(solution(A));  

  </script>

</body>
</html>

Do comment if you have any doubts and suggestions on this JS code.

Note: The All JS Examples codes are tested on the Firefox browser and the Chrome browser.

OS: Windows 10

Code: HTML 5 Version


Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.