Description
You are given a 0-indexed array of integers nums.
A prefix nums[0..i] is sequential if, for all 1 <= j <= i, nums[j] = nums[j - 1] + 1. In particular, the prefix consisting only of nums[0] is sequential.
Return the smallest integer x missing from nums such that x is greater than or equal to the sum of the longest sequential prefix.
Example 1:
Input: nums = [1,2,3,2,5] Output: 6 Explanation: The longest sequential prefix of nums is [1,2,3] with a sum of 6. 6 is not in the array, therefore 6 is the smallest missing integer greater than or equal to the sum of the longest sequential prefix.
Example 2:
Input: nums = [3,4,5,1,12,14,13] Output: 15 Explanation: The longest sequential prefix of nums is [3,4,5] with a sum of 12. 12, 13, and 14 belong to the array while 15 does not. Therefore 15 is the smallest missing integer greater than or equal to the sum of the longest sequential prefix.
Constraints:
1 <= nums.length <= 501 <= nums[i] <= 50
Solutions
This function finds the smallest missing integer that is greater than or equal to the sum of the longest sequential prefix of the array. It starts by initializing sum with the first element, then loops through the array adding each element to sum as long as the values keep increasing by exactly 1 (e.g. [3, 4, 5]); the moment a number breaks that consecutive chain, the loop stops with break. At that point sum holds the total of the longest consecutive run at the start of the array. The code then builds a Set from nums for fast lookups and repeatedly increments sum while it already exists in the set, so the first value not present in the array is returned as the answer.
/**
* @param {number[]} nums
* @return {number}
*/
var missingInteger = function(nums) {
let sum = nums[0];
for (let j = 1; j < nums.length; j++) {
if (nums[j - 1] + 1 !== nums[j]) {
break;
}
sum += nums[j];
}
const set = new Set(nums);
while (set.has(sum)) {
sum++;
}
return sum;
};