Smallest Missing Value at or Above a Sequential Prefix Sum
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
# Smallest Missing Value at or Above a Sequential Prefix Sum
You are given a 0-indexed integer array `nums`. A prefix `nums[0..i]` is sequential if every successive element is exactly one more than its predecessor: `nums[j] = nums[j - 1] + 1` for all `1 <= j <= i`. The prefix containing only `nums[0]` is always sequential.
Let `S` be the sum of the longest sequential prefix. Return the smallest integer `x` that does not occur anywhere in `nums` and satisfies `x >= S`.
### Examples
**Example 1**
```text
Input: nums = [2,3,1,5,6]
Output: 7
```
The longest sequential prefix is `[2,3]`, with sum `5`; the next value `1` breaks the required progression. Both `5` and `6` appear in the full array, while `7` does not. Hence the answer is `7`.
**Example 2**
```text
Input: nums = [4,5,2,10]
Output: 9
```
The longest sequential prefix is `[4,5]`, with sum `9`. Since `9` is missing, it is returned immediately. The condition permits equality with the prefix sum.
### Constraints
- `1 <= nums.length <= 50`.
- `1 <= nums[i] <= 50`.
### Clarifying Questions
- Must the sequential segment start at index zero? Yes; it is a prefix, not an arbitrary subarray.
- Does a later run continue the prefix after a mismatch? No; the prefix ends at the first broken `+1` step.
- Is `x` strictly greater than `S`? No; the required comparison is greater than or equal to `S`.
- Is membership checked only in the prefix? No; `x` must be absent from the entire array.
- May the input be reordered before determining the prefix? No; the prefix uses the original order.
### C++ Interface
```cpp
class Solution {
public:
int missingInteger(vector<int>& nums) {
}
};
```
### Reasoning Checkpoints
- Find the longest prefix under the exact consecutive-increment rule.
- Preserve the inclusive threshold and check absence across the whole input.
- Explain why the search stops at the smallest eligible missing value.
```hint Separate the prefix rule from membership
First compute the prefix sum without changing the input order. Then test consecutive candidates starting at that sum against a presence table for the entire array.
```
Overview: Return the smallest value absent from the whole array that is at least the sum of its longest original-order prefix increasing by exactly one at each step.