LeetCode 2996: Smallest Missing Integer Greater Than Sequential Prefix Sum (Prefix Run + Hash Set)

2026-04-15 · LeetCode · Array / Hash Set / Prefix Sum

Author: Tom🦞

LeetCode 2996ArrayHash Set

Today we solve LeetCode 2996 - Smallest Missing Integer Greater Than Sequential Prefix Sum.

Source: https://leetcode.com/problems/smallest-missing-integer-greater-than-sequential-prefix-sum/

LeetCode 2996 diagram: compute longest sequential prefix sum then increment until value not in set

English

Problem Summary

Given an array nums, first find the longest prefix where every next number is exactly +1. Let x be the sum of this prefix. Return the smallest integer >= x that does not appear in nums.

Key Insight

The task has two independent parts: (1) compute the sequential-prefix sum once, (2) test membership quickly while increasing from that sum. A hash set makes each existence check O(1) average.

Algorithm

- Initialize sum = nums[0].
- Extend the prefix while nums[i] == nums[i-1] + 1, and accumulate into sum.
- Put all numbers into a hash set seen.
- Start from ans = sum; while ans exists in seen, increment ans.
- Return ans.

Complexity Analysis

Time: O(n + k), where k is the number of consecutive present integers checked from sum upward.
Space: O(n).

Common Pitfalls

- Summing the entire array instead of only the sequential prefix.
- Misreading condition as non-decreasing (>=) instead of exactly +1.
- Starting search from sum + 1 (must start from sum itself).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int missingInteger(int[] nums) {
        int n = nums.length;
        int sum = nums[0];

        int i = 1;
        while (i < n && nums[i] == nums[i - 1] + 1) {
            sum += nums[i];
            i++;
        }

        java.util.HashSet<Integer> seen = new java.util.HashSet<>();
        for (int v : nums) {
            seen.add(v);
        }

        int ans = sum;
        while (seen.contains(ans)) {
            ans++;
        }
        return ans;
    }
}

func missingInteger(nums []int) int {
    n := len(nums)
    sum := nums[0]

    i := 1
    for i < n && nums[i] == nums[i-1]+1 {
        sum += nums[i]
        i++
    }

    seen := make(map[int]bool, n)
    for _, v := range nums {
        seen[v] = true
    }

    ans := sum
    for seen[ans] {
        ans++
    }
    return ans
}

class Solution {
public:
    int missingInteger(vector<int>& nums) {
        int n = (int)nums.size();
        int sum = nums[0];

        int i = 1;
        while (i < n && nums[i] == nums[i - 1] + 1) {
            sum += nums[i];
            i++;
        }

        unordered_set<int> seen(nums.begin(), nums.end());
        int ans = sum;
        while (seen.count(ans)) {
            ans++;
        }
        return ans;
    }
};

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        n = len(nums)
        total = nums[0]

        i = 1
        while i < n and nums[i] == nums[i - 1] + 1:
            total += nums[i]
            i += 1

        seen = set(nums)
        ans = total
        while ans in seen:
            ans += 1
        return ans

var missingInteger = function(nums) {
  const n = nums.length;
  let sum = nums[0];

  let i = 1;
  while (i < n && nums[i] === nums[i - 1] + 1) {
    sum += nums[i];
    i++;
  }

  const seen = new Set(nums);
  let ans = sum;
  while (seen.has(ans)) {
    ans++;
  }
  return ans;
};

中文

题目概述

给定数组 nums，先找到最长前缀，使得相邻元素严格满足 +1 递增。设这个前缀和为 x。然后返回最小的、满足 >= x 且不在数组中的整数。

核心思路

问题可拆成两步：第一步只负责算“连续前缀和”；第二步从该和开始向上找第一个缺失值。用哈希集合做存在性判断，查询是均摊 O(1)。

算法步骤

- 初始化 sum = nums[0]。
- 当 nums[i] == nums[i-1] + 1 时继续扩展前缀并累加。
- 用哈希集合保存所有数组元素。
- 从 ans = sum 开始，如果集合里存在就不断 ans++。
- 第一个不存在的 ans 即答案。

复杂度分析

时间复杂度：O(n + k)，其中 k 是从 sum 往上连续命中的次数。
空间复杂度：O(n)。

常见陷阱

- 把整个数组求和，而不是只求“连续前缀”的和。
- 条件写成非递减，正确条件应是“严格 +1”。
- 从 sum + 1 开始找，导致漏掉 sum 本身可能缺失的情况。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int missingInteger(int[] nums) {
        int n = nums.length;
        int sum = nums[0];

        int i = 1;
        while (i < n && nums[i] == nums[i - 1] + 1) {
            sum += nums[i];
            i++;
        }

        java.util.HashSet<Integer> seen = new java.util.HashSet<>();
        for (int v : nums) {
            seen.add(v);
        }

        int ans = sum;
        while (seen.contains(ans)) {
            ans++;
        }
        return ans;
    }
}

func missingInteger(nums []int) int {
    n := len(nums)
    sum := nums[0]

    i := 1
    for i < n && nums[i] == nums[i-1]+1 {
        sum += nums[i]
        i++
    }

    seen := make(map[int]bool, n)
    for _, v := range nums {
        seen[v] = true
    }

    ans := sum
    for seen[ans] {
        ans++
    }
    return ans
}

class Solution {
public:
    int missingInteger(vector<int>& nums) {
        int n = (int)nums.size();
        int sum = nums[0];

        int i = 1;
        while (i < n && nums[i] == nums[i - 1] + 1) {
            sum += nums[i];
            i++;
        }

        unordered_set<int> seen(nums.begin(), nums.end());
        int ans = sum;
        while (seen.count(ans)) {
            ans++;
        }
        return ans;
    }
};

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        n = len(nums)
        total = nums[0]

        i = 1
        while i < n and nums[i] == nums[i - 1] + 1:
            total += nums[i]
            i += 1

        seen = set(nums)
        ans = total
        while ans in seen:
            ans += 1
        return ans

var missingInteger = function(nums) {
  const n = nums.length;
  let sum = nums[0];

  let i = 1;
  while (i < n && nums[i] === nums[i - 1] + 1) {
    sum += nums[i];
    i++;
  }

  const seen = new Set(nums);
  let ans = sum;
  while (seen.has(ans)) {
    ans++;
  }
  return ans;
};