2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

Array
Hash Table
Simulation

TIME

O(n + A)

SPACE

O(n)

Intuition

A "sequential prefix" must start at index 0, so there's exactly one longest such prefix: the maximal run from the front where each element is one more than the previous. Sum it, then walk upward from that sum until hitting a value not in nums.

Approach

Start with total = nums[0]. Extend while nums[j] == nums[j-1] + 1, adding each element to total; stop at the first break.
Put nums into a set.
From x = total upward, return the first x not in the set.

The search terminates quickly: values are bounded by 50, so any x above 50 is immediately missing.

Complexity

Time: O(n + A) where A is how far the upward scan goes (bounded by ~51 here)
Space: O(n), the membership set

Edge Cases

Single element → the prefix is just nums[0], sum is that value
Prefix breaks immediately (nums[1] != nums[0]+1) → sum is nums[0]
The sum itself may exceed all values in nums → answer is the sum
Consecutive values above the sum must be skipped (Example 2: 12, 13, 14 present → 15)
Note the prefix must start at index 0; a longer sequential run later in the array does not count

Code

from typing import List


class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        """
        2996. Smallest Missing Integer Greater Than Sequential Prefix Sum
        Time: O(n + A)
        Space: O(n)
        """
        # Longest sequential prefix (must start at index 0).
        total = nums[0]
        for j in range(1, len(nums)):
            if nums[j] != nums[j - 1] + 1:
                break
            total += nums[j]

        present = set(nums)
        x = total
        while x in present:
            x += 1
        return x

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

/**
 * 2996. Smallest Missing Integer Greater Than Sequential Prefix Sum
 * Time: O(n + A)
 * Space: O(n)
 */
class Solution {
    public int missingInteger(int[] nums) {
        // Longest sequential prefix (must start at index 0).
        int total = nums[0];
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[j - 1] + 1) {
                break;
            }
            total += nums[j];
        }

        Set<Integer> present = new HashSet<>();
        for (int x : nums) {
            present.add(x);
        }

        int x = total;
        while (present.contains(x)) {
            x++;
        }
        return x;
    }
}