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
Afrom the start, and for each valueA[i], ifA[i] - 1is a valid index in the array, then repeatedly swapA[i]andA[A[i] - 1]untilA[i]is in its correct place (value equal toi + 1), orA[i]andA[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 isi + 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:
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 or 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