# Smallest Missing Integer Greater Than Sequential Prefix Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/smallest-missing-integer-greater-than-sequential-prefix-sum)
Canonical: https://scaleengineer.com/dsa/problems/smallest-missing-integer-greater-than-sequential-prefix-sum
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
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`

# Approaches
## Brute-Force Search
This approach first calculates the sum of the longest sequential prefix. Then, it iteratively checks for the smallest integer, starting from the calculated sum, that is not present in the input array. The check for presence is done by linearly scanning the entire array for each candidate integer.
**Time:** O(N^2), where N is the number of elements in `nums`. Calculating the prefix sum takes O(N). The search for the missing integer involves a loop that can run up to N+1 times in the worst case, and inside this loop, we scan the array again, which takes O(N). This results in a total complexity of O(N + N*N) = O(N^2). · **Space:** O(1), as we only use a few variables to store the sum and the candidate integer, regardless of the input size.
**Pros:** Simple to understand and implement.; Space-efficient, as it uses O(1) extra space.
**Cons:** The time complexity is quadratic, O(N^2), which is inefficient for larger inputs.; It repeatedly scans the input array, which is redundant.
### Explanation
The method involves two main steps. First, we determine the longest sequential prefix and compute its sum. We start with the first element as the initial sum and iterate from the second element. As long as the current element is one greater than the previous, we extend the sequential prefix and add the current element to our running sum. We stop as soon as this condition is violated.

Second, we find the smallest integer `x` that is greater than or equal to the computed sum and is not present in the `nums` array. We start by setting our candidate `x` to the sum. We then enter a loop. In each iteration, we perform a linear scan through the `nums` array to see if `x` is present. If it is, we increment `x` and repeat the scan. If we complete a scan without finding `x`, we have found our answer, and we return `x`.

```java
class Solution {
    public int missingInteger(int[] nums) {
        // Step 1: Calculate the sum of the longest sequential prefix
        long prefixSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] + 1) {
                prefixSum += nums[i];
            } else {
                break;
            }
        }

        // Step 2: Find the smallest missing integer >= prefixSum
        int x = (int) prefixSum;
        while (true) {
            boolean found = false;
            for (int num : nums) {
                if (num == x) {
                    found = true;
                    break;
                }
            }
            if (found) {
                x++;
            } else {
                return x;
            }
        }
    }
}
```
### Algorithm
1.  **Calculate Prefix Sum**: Initialize `prefixSum = nums[0]`. Iterate from `i = 1` to `n-1`. If `nums[i] == nums[i-1] + 1`, add `nums[i]` to `prefixSum`. Otherwise, break the loop.
2.  **Iterative Search**: Initialize a candidate integer `x` with the value of `prefixSum`.
3.  Start a `while(true)` loop.
4.  Inside the loop, check if `x` exists in the `nums` array by iterating through `nums` from start to end.
5.  If `x` is found, increment `x` and continue to the next iteration.
6.  If `x` is not found after checking all elements, it is the smallest missing integer. Return `x`.

## Optimized Search with a HashSet
This approach improves upon the brute-force method by optimizing the search for the missing integer. After calculating the prefix sum, it first stores all elements of the input array into a `HashSet`. This allows for checking the existence of an integer in average O(1) time, significantly speeding up the search process.
**Time:** O(N). Calculating the prefix sum is O(N). Populating the `HashSet` is O(N). The final search loop runs at most N+1 times, with each check being an O(1) operation on average. Thus, the total time complexity is O(N). · **Space:** O(N), where N is the number of elements in `nums`. This space is used to store the elements in the `HashSet`.
**Pros:** Much more time-efficient than the brute-force approach, with a linear time complexity of O(N).; The logic remains relatively simple.
**Cons:** Requires extra space proportional to the number of elements in the input array, O(N).
### Explanation
This method enhances the previous one by trading space for time. The first step, calculating the sum of the longest sequential prefix, remains unchanged.

Next, to accelerate the search for the missing number, we first populate a `HashSet` with all the elements from the `nums` array. This preprocessing step takes O(N) time but allows subsequent existence checks (`contains` operations) to be performed in average O(1) time.

Finally, we initialize our candidate integer `x` to the calculated prefix sum. We then repeatedly check if `x` is in our `HashSet`. As long as it is, we increment `x`. The first value of `x` that is not found in the set is our answer.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int missingInteger(int[] nums) {
        // Step 1: Calculate the sum of the longest sequential prefix
        long prefixSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] + 1) {
                prefixSum += nums[i];
            } else {
                break;
            }
        }

        // Step 2: Store all numbers in a HashSet for O(1) lookup
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        // Step 3: Find the smallest missing integer >= prefixSum
        int x = (int) prefixSum;
        while (numSet.contains(x)) {
            x++;
        }
        return x;
    }
}
```
### Algorithm
1.  **Calculate Prefix Sum**: This step is the same as the brute-force approach. Find the sum of the longest sequential prefix.
2.  **Populate HashSet**: Create a `HashSet<Integer>` and add all elements from the `nums` array into it. This allows for O(1) average time complexity for checking the existence of an element.
3.  **Optimized Search**: Initialize a candidate integer `x` with the value of `prefixSum`.
4.  Use a `while` loop that continues as long as `set.contains(x)` is true.
5.  Inside the loop, increment `x`.
6.  When the loop terminates, `x` is the first integer not found in the set, so return `x`.

## Most Efficient Search with a Boolean Array
This is the most efficient approach, leveraging the problem's constraints on the values within the `nums` array (`1 <= nums[i] <= 50`). Instead of a `HashSet`, it uses a boolean array as a direct address table (or frequency map) to track the presence of numbers. This provides O(1) lookup time like a `HashSet` but with constant space complexity, as the array size is fixed by the constraints and does not depend on the input size `N`.
**Time:** O(N). Calculating the prefix sum is O(N). Populating the boolean array is O(N). The final `while` loop runs at most a constant number of times (at most 51 times), which is an O(1) operation. The total time complexity is O(N + N + 1) = O(N). · **Space:** O(1). The boolean array has a fixed size (51) determined by the problem constraints on the values of `nums[i]`, not by the length of the input array `N`.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1), as the extra space used is constant.; Extremely fast in practice due to direct array indexing, avoiding hashing overhead.
**Cons:** This approach's efficiency relies on the constraint that the values in `nums` are within a small, fixed range. It is not a general-purpose solution for arrays with large or unbounded integer values.
### Explanation
This approach is the most optimized, taking full advantage of the problem's constraints. The first step of calculating the prefix sum is the same.

The key optimization is in how we check for the presence of numbers. Since all numbers in `nums` are between 1 and 50, we can use a simple boolean array of size 51 as a direct mapping. We create `boolean[] present = new boolean[51]` and iterate through `nums`, setting `present[num] = true` for each number `num` in the input.

With this `present` array, checking for a number's existence is an O(1) operation. We initialize our candidate `x` to the prefix sum. We then increment `x` as long as it is within the bounds of our `present` array (i.e., `x <= 50`) and is marked as present (`present[x]` is true). The loop stops when `x` is a number not present in `nums` or when `x` exceeds 50. In either case, this final value of `x` is the smallest missing integer we are looking for, because any number greater than 50 is guaranteed not to be in the original `nums` array.

```java
class Solution {
    public int missingInteger(int[] nums) {
        // Step 1: Calculate the sum of the longest sequential prefix
        long prefixSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] + 1) {
                prefixSum += nums[i];
            } else {
                break;
            }
        }

        // Step 2: Mark numbers present in the input array
        boolean[] present = new boolean[51];
        for (int num : nums) {
            if (num <= 50) {
                present[num] = true;
            }
        }

        // Step 3: Find the smallest missing integer >= prefixSum
        int x = (int) prefixSum;
        while (x <= 50 && present[x]) {
            x++;
        }
        
        return x;
    }
}
```
### Algorithm
1.  **Calculate Prefix Sum**: Same as the previous approaches.
2.  **Create Boolean Presence Array**: Create a boolean array, e.g., `present` of size 51, since `1 <= nums[i] <= 50`. Initialize it to all `false`.
3.  **Mark Present Numbers**: Iterate through `nums`. For each `num`, if `num <= 50`, set `present[num] = true`.
4.  **Efficient Search**: Initialize `x` with `prefixSum`.
5.  Use a `while` loop: `while (x <= 50 && present[x])`.
6.  Inside the loop, increment `x`.
7.  After the loop, `x` is the answer. If `x` became greater than 50, it's guaranteed to be missing. If it's less than or equal to 50, it's the first number not marked as present.

# Solutions
### Java

```java
class Solution { public int missingInteger ( int [] nums ) { int s = nums [ 0 ]; for ( int j = 1 ; j < nums . length && nums [ j ] == nums [ j - 1 ] + 1 ; ++ j ) { s += nums [ j ]; } boolean [] vis = new boolean [ 51 ]; for ( int x : nums ) { vis [ x ] = true ; } for ( int x = s ;; ++ x ) { if ( x >= vis . length || ! vis [ x ]) { return x ; } } } }
```

### CPP

```cpp
class Solution { public: int missingInteger ( vector < int >& nums ) { int s = nums [ 0 ]; for ( int j = 1 ; j < nums . size () && nums [ j ] == nums [ j - 1 ] + 1 ; ++ j ) { s += nums [ j ]; } bitset < 51 > vis ; for ( int x : nums ) { vis [ x ] = 1 ; } for ( int x = s ;; ++ x ) { if ( x >= 51 || ! vis [ x ]) { return x ; } } } };
```

### Python

```python
class Solution : def missingInteger ( self , nums : List [ int ]) -> int : s , j = nums [ 0 ], 1 while j < len ( nums ) and nums [ j ] == nums [ j - 1 ] + 1 : s += nums [ j ] j += 1 vis = set ( nums ) for x in count ( s ): if x not in vis : return x
```