2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

Problem Overview

Take the longest prefix that stays consecutive (+1 each step) starting at nums[0], sum it, then walk upward from that sum until you hit a value missing from the array.

Intuition

Take the longest prefix that stays consecutive (+1 each step) starting at nums[0], sum it, then walk upward from that sum until you hit a value missing from the array. With values capped at 50, a bool[51] is enough for membership, and any candidate past 50 is automatically missing.

Algorithm

1Mark seen[x] = true for every nums value (x in 1..50).
2ans = nums[0]; extend while nums[i] == nums[i-1] + 1, adding into ans.
3While ans <= 50 and seen[ans], increment ans.
4Return ans.

Example Walkthrough

Input: nums = [1, 2, 3, 2, 5]

1.Longest sequential prefix [1,2,3] sums to 6.
2.6 is not in the array, so the answer is 6.

Output: 6

Common Pitfalls

•Only the prefix from index 0 matters - later consecutive runs do not count.
•A single-element prefix is always sequential.
•Constraints guarantee 1 <= nums[i] <= 50, so bool[51] is safe.
•If the sum already exceeds 50, return it immediately - it cannot appear in nums.

2996.cs

// Approach: Sum the longest consecutive prefix nums[0], nums[0]+1, ... then find
// the smallest integer >= that sum not present in nums. Values are in 1..50, so
// a bool[51] marks presence in O(1) space; if the candidate exceeds 50 it cannot
// appear in nums and is returned immediately.
// Complexity: O(n) time and O(1) space.
public class Solution
{
    public int MissingInteger(int[] nums)
    {
        bool[] seen = new bool[51];
        foreach (int x in nums)
            seen[x] = true;

        int ans = nums[0];
        for (int i = 1; i < nums.Length && nums[i] == nums[i - 1] + 1; ++i)
            ans += nums[i];

        while (ans <= 50 && seen[ans])
            ++ans;

        return ans;
    }
}

Was this solution helpful?