2996. Smallest Missing Integer Greater Than Sequential Prefix Sum
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 <= 50
1 <= nums[i] <= 50
Solutions
Solution 1: Simulation + Hash Table
First, we calculate the longest prefix sum $s$ of the array $nums$. Then, starting from $s$, we enumerate the integer $x$. If $x$ is not in the array $nums$, then $x$ is the answer. Here, we can use a hash table to quickly determine whether an integer is in the array $nums$.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array $nums$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|