Skip to main content
Talentd

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

EasyArrayHash TableSorting14 min readAsked at: Microsoft, Google
Practice this problem

Problem Statement

You are given a 0-indexed array of integers nums.

A prefix nums[0..i] is sequential if, for all 1 <= j <= i, nums[j] = nums[j - 1] + 1. In particular, the prefix consisting only of nums[0] is sequential.

Return the smallest integer x missing from nums such that x is greater than or equal to the sum of the longest sequential prefix.

 

Example 1:

Input: nums = [1,2,3,2,5]
Output: 6
Explanation: The longest sequential prefix of nums is [1,2,3] with a sum of 6. 6 is not in the array, therefore 6 is the smallest missing integer greater than or equal to the sum of the longest sequential prefix.

Example 2:

Input: nums = [3,4,5,1,12,14,13]
Output: 15
Explanation: The longest sequential prefix of nums is [3,4,5] with a sum of 12. 12, 13, and 14 belong to the array while 15 does not. Therefore 15 is the smallest missing integer greater than or equal to the sum of the longest sequential prefix.

 

Constraints:

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

Approach Overview

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.

Approach 1: Approach 1: Identify Longest Sequential Prefix and Check Missing Integer

This approach involves identifying the longest sequential prefix of the array and computing its sum. Once we have this sum, we find the smallest integer greater than or equal to this sum that is not present within the array.

This C solution first calculates the sum of the longest sequential prefix and then iterates from this sum upwards to find the first missing integer not in the array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the length of the array (max 50) and m is the number of sequence checks.
Space Complexity: O(1), constant space is used aside from input data.

Try this approach in the editor →

Approach 2: Approach 2: Tracking Sequence with a Sorted Array

Another approach is to sort the array, which simplifies the identification of longest or existing sequences. After determining the sequence sum in sorted form, the subsequent checks for missing integers are straightforward.

By sorting the array initially, we simplify the tracking of sequences. The C code checks from the sum of identified sequence for missing integers.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting, worst-case lookup for missing integer is linear.
Space Complexity: O(1), aside from input.

Try this approach in the editor →

Approach 3: Simulation + Hash Table

First, we calculate the longest prefix sum s of the array nums. Then, starting from s, we enumerate the integer x. If x is not in the array nums, then x is the answer. Here, we can use a hash table to quickly determine whether an integer is in the array nums.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Identify Longest Sequential Prefix and Check Missing Integer

Time Complexity: O(n * m), where n is the length of the array (max 50) and m is the number of sequence checks.
Space Complexity: O(1), constant space is used aside from input data.

Approach 2: Tracking Sequence with a Sorted Array

Time Complexity: O(n log n) due to sorting, worst-case lookup for missing integer is linear.
Space Complexity: O(1), aside from input.

Simulation + Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Identify Sequential Prefix + Hash Set LookupO(n)O(n)General case. Best performance with constant-time membership checks.
Sort Array and Scan for Missing IntegerO(n log n)O(1) extraWhen extra memory is limited and modifying the array is acceptable.

Video Solution

Smallest Missing Integer Greater Than Sequential Prefix Sum | Tricky Statement to Understand • Aryan Mittal • 2,059 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Smallest Missing Integer Greater Than Sequential Prefix Sum easy or hard?
The problem is classified as Easy. It mainly tests careful array traversal and efficient lookup using a hash set. Once the sequential prefix condition is recognized, the remaining step is a straightforward missing-number search.
Smallest Missing Integer Greater Than Sequential Prefix Sum Python/Java solution
Python and Java implementations typically compute the sequential prefix sum with a loop, store elements in a set or HashSet, and increment the candidate value until it is not present. Both languages achieve O(n) time complexity with O(n) additional space.
How to solve Smallest Missing Integer Greater Than Sequential Prefix Sum in O(n)?
First iterate from the beginning of the array while elements increase by exactly one to determine the sequential prefix and compute its sum. Insert all numbers into a hash set. Starting from the prefix sum, repeatedly check if the value exists in the set and increment until a missing number appears. This keeps the entire process linear.
What is the best approach for Smallest Missing Integer Greater Than Sequential Prefix Sum?
The most efficient approach computes the longest sequential prefix, calculates its sum, and stores all array values in a hash set. Starting from the prefix sum, increment until a value is not found in the set. Hash lookups are O(1), so the overall complexity is O(n) time with O(n) space.
Is Smallest Missing Integer Greater Than Sequential Prefix Sum asked at Google/Amazon/Meta?
This problem follows common patterns seen in technical interviews: prefix processing, hash set membership checks, and missing-number detection. Similar problems appear in interviews at companies like Amazon and Google where candidates must combine array traversal with hash-based lookups.
What data structure is used in Smallest Missing Integer Greater Than Sequential Prefix Sum?
A hash set is the primary data structure used in the optimal solution. It provides constant-time membership checks when searching for the smallest integer that does not appear in the array. The array itself is scanned to detect the sequential prefix.
What is the time complexity of Smallest Missing Integer Greater Than Sequential Prefix Sum?
The optimal solution runs in O(n) time. One pass identifies the longest sequential prefix and builds a hash set of values, and additional checks for the missing integer are constant-time lookups. Space complexity is O(n) due to storing the elements in a hash set.

Ready to solve this problem?

Practice Smallest Missing Integer Greater Than Sequential Prefix Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

First Missing Positive

Next

Longest Common Prefix