Smallest Missing Integer Greater Than Sequential Prefix Sum - Solution & Explanation

Problem Overview: You are given an integer array. First identify the longest prefix where numbers increase sequentially by exactly +1. Compute the sum of that prefix. The task is to return the smallest integer greater than or equal to that sum that does not appear in the array.

The challenge has two parts: detect the longest sequential prefix and then search for the smallest missing integer starting from the prefix sum. Efficient solutions rely on constant-time lookups using a hash table or ordering the numbers with sorting. Since the input is an array, a single pass combined with fast membership checks usually gives the optimal result.

Approach 1: Identify Longest Sequential Prefix and Check Missing Integer (O(n) time, O(n) space)

Scan the array from the start and extend the prefix while nums[i] == nums[i-1] + 1. Accumulate the prefix sum during this pass. Once the sequential prefix ends, insert every value from the array into a hash set for constant-time lookups. Start checking integers from the computed prefix sum. If the value exists in the set, increment and check again. The first value not present is the answer.

The key insight: the prefix sum defines the lower bound for the result, while the hash set quickly tells you whether a candidate value already appears in the array. This avoids repeatedly scanning the array and keeps the search for the missing number efficient.

Approach 2: Tracking Sequence with a Sorted Array (O(n log n) time, O(1) extra space)

Another strategy sorts the array first. After computing the sequential prefix and its sum, iterate through the sorted numbers to see if the candidate value exists. If the prefix sum is present, increment it until you encounter a gap. Because the array is sorted, duplicates and smaller values are easy to skip while advancing the candidate.

This approach trades extra runtime for reduced auxiliary memory. Sorting organizes the values so you can detect the first missing integer through a linear scan. It works well when modifying the input array is allowed and additional memory for a hash structure is undesirable.

Recommended for interviews: The hash set approach is typically expected. It separates the problem into two clear steps: compute the sequential prefix sum, then perform fast membership checks. Time complexity stays O(n) with O(n) space, which is optimal for arbitrary arrays. Showing the sorting alternative demonstrates awareness of space–time tradeoffs, but the hash-based solution best reflects strong problem-solving instincts.