LeetCode 2996 - Smallest Missing Integer Greater Than Sequential Prefix Sum

LeetCode Problem 2996

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

The problem asks us to find the smallest missing integer in the array that is greater than or equal to the sum of the longest sequential prefix.

A sequential prefix means the beginning part of the array where every number increases by exactly 1 compared to the previous number. Formally, for a prefix nums[0..i], every element must satisfy:

nums[j] = nums[j - 1] + 1

for every 1 <= j <= i.

The prefix always starts at index 0, and even a single element, nums[0], counts as a valid sequential prefix.

The task can be broken into two parts:

1. Find the longest sequential prefix and compute its sum.
2. Starting from that sum, find the smallest integer not present in the array.

For example, in nums = [1,2,3,2,5], the longest sequential prefix is [1,2,3] because 2 = 1 + 1 and 3 = 2 + 1, but the next element 2 breaks the sequence. The prefix sum is 6. Since 6 does not exist in the array, the answer is 6.

The constraints are very small:

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

These constraints tell us that efficiency is not a major concern. Even a less optimized solution would pass comfortably. However, we should still aim for a clean and efficient implementation.

There are several important edge cases to consider. The array may contain only one element, meaning the sequential prefix consists of that single number. The prefix may include the entire array if every element is consecutive. The prefix sum itself may already exist in the array, requiring us to continue searching upward until we find a missing value. Duplicate values or gaps in the array can also terminate the sequential prefix early.

Approaches

Brute Force Approach

A brute-force solution would first compute the sum of the longest sequential prefix. Then, starting from that sum, repeatedly check whether the current number exists in the array by scanning the entire array linearly.

If the number exists, increment it and try again. Continue until finding a value that does not appear in nums.

This works because we explicitly test every candidate integer in increasing order, guaranteeing that the first missing one is the smallest valid answer.

However, checking membership by repeatedly scanning the array is inefficient. Each lookup costs O(n), and in the worst case we may test several consecutive numbers.

Key Insight for an Optimal Solution

The key observation is that we need fast membership checking while searching for the smallest missing integer.

A hash set is ideal because it provides average O(1) lookup time.

The algorithm becomes:

1. Compute the sum of the longest sequential prefix.
2. Store all elements in a set.
3. Starting from the prefix sum, repeatedly increment until finding a number not in the set.

Since set membership is constant time, the search becomes very efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly scans the array to test existence
Optimal	O(n)	O(n)	Uses a hash set for constant-time membership checks

Algorithm Walkthrough

1. Initialize the prefix sum using the first element.

Since a single element is always considered a sequential prefix, start with:

sequential_sum = nums[0] 2. Traverse the array from index 1.

For each element, check whether it continues the sequential pattern:

nums[i] == nums[i - 1] + 1

If true, add the value to the running sum because the prefix remains sequential.

If false, stop immediately because the longest sequential prefix has ended. 3. Store all numbers in a hash set.

This allows constant-time membership checking when searching for missing integers. 4. Start checking from the sequential prefix sum.

If the sum exists in the set, increment it and try again.

Continue until finding a number not present in the set. 5. Return the first missing integer.

Since we check candidates in increasing order, the first missing value is guaranteed to be the smallest valid answer.

Why it works

The algorithm works because it separates the problem into two logically independent steps.

First, it correctly identifies the longest sequential prefix by continuing only while each number increases by exactly 1. Once the sequence breaks, no longer prefix can be valid.

Second, beginning at the prefix sum ensures every candidate satisfies the requirement of being greater than or equal to the sum. Since candidates are checked in ascending order and set lookups are exact, the first missing integer found must be the smallest valid answer.

Python Solution

from typing import List

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

        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1] + 1:
                sequential_sum += nums[i]
            else:
                break

        num_set = set(nums)

        while sequential_sum in num_set:
            sequential_sum += 1

        return sequential_sum

The implementation begins by initializing sequential_sum with the first element because a single-element prefix is always sequential.

The for loop walks through the array and checks whether each value continues the consecutive pattern. If the current element equals the previous element plus one, it belongs to the sequential prefix and gets added to the running sum. Otherwise, the loop stops immediately.

Next, the array is converted into a set called num_set. This allows fast membership checks when searching for the answer.

Finally, the while loop repeatedly checks whether the current candidate exists in the set. If it does, the candidate is incremented. Once a missing integer is found, it is returned.

Go Solution

func missingInteger(nums []int) int {
	sequentialSum := nums[0]

	for i := 1; i < len(nums); i++ {
		if nums[i] == nums[i-1]+1 {
			sequentialSum += nums[i]
		} else {
			break
		}
	}

	numSet := make(map[int]bool)
	for _, num := range nums {
		numSet[num] = true
	}

	for numSet[sequentialSum] {
		sequentialSum++
	}

	return sequentialSum
}

The Go implementation follows the same logic as the Python version. Since Go does not have a built-in set type, a map[int]bool is used to simulate a hash set.

There are no concerns about integer overflow because the constraints are extremely small. Even in the maximum case, the sum remains safely within Go's integer range.

The input slice is guaranteed to contain at least one element, so accessing nums[0] is always safe.

Worked Examples

Example 1

Input:

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

Step 1: Find the longest sequential prefix

Index	Value	Sequential?	Running Sum
0	1	Yes, starting element	1
1	2	2 = 1 + 1	3
2	3	3 = 2 + 1	6
3	2	No, sequence breaks	Stop

The longest sequential prefix is:

[1,2,3]

The sum is:

6

Step 2: Search for smallest missing integer

Set contents:

{1,2,3,5}

Candidate	Exists in Set?	Action
6	No	Return 6

Output:

6

Example 2

Input:

nums = [3,4,5,1,12,14,13]

Step 1: Find the longest sequential prefix

Index	Value	Sequential?	Running Sum
0	3	Yes, starting element	3
1	4	4 = 3 + 1	7
2	5	5 = 4 + 1	12
3	1	No, sequence breaks	Stop

The longest sequential prefix is:

[3,4,5]

The sum is:

12

Step 2: Search for smallest missing integer

Set contents:

{1,3,4,5,12,13,14}

Candidate	Exists in Set?	Action
12	Yes	Increment
13	Yes	Increment
14	Yes	Increment
15	No	Return 15

Output:

15

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to compute the prefix sum, one pass to build the set, and at most O(n) membership checks
Space	O(n)	The hash set stores all elements from the array

Although the algorithm includes several loops, each element is processed only a constant number of times. The membership checks are efficient because hash set lookups are average O(1). Since the array size is at most 50, the solution runs comfortably within limits.

Test Cases

from typing import List

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

        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1] + 1:
                sequential_sum += nums[i]
            else:
                break

        num_set = set(nums)

        while sequential_sum in num_set:
            sequential_sum += 1

        return sequential_sum

solution = Solution()

assert solution.missingInteger([1, 2, 3, 2, 5]) == 6  # Provided example 1
assert solution.missingInteger([3, 4, 5, 1, 12, 14, 13]) == 15  # Provided example 2
assert solution.missingInteger([5]) == 6  # Single element array
assert solution.missingInteger([1, 2, 3, 4]) == 10  # Entire array is sequential
assert solution.missingInteger([1, 2, 4, 5]) == 3  # Prefix breaks early
assert solution.missingInteger([2, 3, 4, 9]) == 10  # Prefix sum not in array
assert solution.missingInteger([1, 2, 3, 6]) == 7  # Prefix sum exists
assert solution.missingInteger([10, 11, 12, 33]) == 34  # Multiple increments required
assert solution.missingInteger([7, 7, 7]) == 8  # Duplicate values break prefix immediately
assert solution.missingInteger([1, 2, 3, 6, 7, 8]) == 9  # Sequential later does not matter

Test	Why
[1,2,3,2,5]	Validates provided example with immediate missing sum
[3,4,5,1,12,14,13]	Validates repeated increments before finding answer
[5]	Tests smallest valid input size
[1,2,3,4]	Tests when the entire array is sequential
[1,2,4,5]	Ensures prefix stops at first break
[2,3,4,9]	Tests when prefix sum is already missing
[1,2,3,6]	Verifies increment when sum exists
[10,11,12,33]	Tests larger values and sequential sum handling
[7,7,7]	Ensures duplicate values terminate prefix correctly
[1,2,3,6,7,8]	Confirms only the prefix matters, not later sequences

Edge Cases

Single Element Array

When the input contains only one number, the longest sequential prefix is simply that element itself. A naive implementation might incorrectly assume at least two elements exist and cause an index error.

For example:

[5]

The prefix sum is 5, and since 5 exists in the array, the answer becomes 6. The implementation handles this naturally because the loop starts from index 1, which never executes for a one-element array.

Prefix Breaks Immediately

The sequence may stop after the first element if the second element is not exactly one greater.

For example:

[7, 7, 7]

The sequential prefix is only [7] because the second 7 is not equal to 7 + 1. The implementation correctly breaks out of the loop immediately and proceeds using a prefix sum of 7.

Prefix Sum Already Exists Multiple Times

The computed prefix sum may already exist in the array, requiring several increments before finding a missing value.

For example:

[3,4,5,1,12,14,13]

The prefix sum is 12, but 12, 13, and 14 all exist. A buggy implementation might stop too early or fail to repeatedly increment. The while loop ensures we continue searching until the first truly missing integer is found.