Smallest Missing Integer Greater Than Sequential Prefix Sum solution and explanation
Google
9 more videos on this problem
Smallest Missing Integer Greater Than Sequential Prefix Sum | Tricky Statement to UnderstandAryan Mittal · 5:15 · 2K views
Smallest Missing Integer Greater Than Sequential Prefix Sum || Prefix sum + Sorting 🔥Ayush Rao · 4:38 · 913 views
100157. Smallest Missing Integer Greater Than Sequential Prefix Sum || Leetcode Byweekly ContestLegend Creatz · 0:29 · 872 views
Leetcode | 2996. Smallest Missing Integer Greater Than Sequential Prefix Sum | Easy | Java SolutionDeveloper Docs · 12:05 · 763 views
100157. Smallest Missing Integer Greater Than Sequential Prefix Sum || Leetcode Byweekly Contestsilent coder · 0:35 · 423 views
2996. Smallest Missing Integer Greater Than Sequential Prefix Sum (Leetcode Easy)Programming Live with Larry · 6:56 · 333 views
Smallest Missing Integer Greater Than Sequential Prefix Sum | Set | BiWeekly 121Tech Courses · 6:03 · 149 views
Smallest Missing Integer Greater Than Sequential Prefix Sum | LeetCode Problem 2996 SolutionRaj Kumar Mahto · 2:17 · 131 views
Leetcode 10031 || Smallest Missing Integer Greater Than Sequential Prefix Sum || Biweekly ContestKomal Pal · 9:12 · 119 views
Python : Smallest Missing Integer Greater Than Sequential PrefixGrow with Data · 15:35 · 151 views
The problem
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 <= 501 <= 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.
def smallest_missing_integer(nums):
longest_seq_sum = nums[0]
current_seq_sum = nums[0]
for i in range(1, len(nums)):
if nums[i] == nums[i - 1] + 1:
current_seq_sum += nums[i]
else:
break
longest_seq_sum = current_seq_sum
num_set = set(nums)
for i in range(longest_seq_sum, 51):
if i not in num_set:
return i
return longest_seq_sum + 1
nums = [3, 4, 5, 1, 12, 14, 13]
print(smallest_missing_integer(nums))import java.util.HashSet;
import java.util.Set;
public class SmallestMissingInteger {
public static int smallestMissingInteger(int[] nums) {
int longestSeqSum = nums[0];
int currentSeqSum = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1] + 1) {
currentSeqSum += nums[i];
} else {
break;
}
}
longestSeqSum = currentSeqSum;
Set<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
for (int i = longestSeqSum; i <= 50; i++) {
if (!numSet.contains(i)) {
return i;
}
}
return longestSeqSum + 1;
}
public static void main(String[] args) {
int[] nums = {3, 4, 5, 1, 12, 14, 13};
System.out.println(smallestMissingInteger(nums));
}
}#include <iostream>
#include <vector>
#include <unordered_set>
int smallest_missing_integer(std::vector<int>& nums) {
int longestSeqSum = nums[0];
int currentSeqSum = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
if (nums[i] == nums[i-1] + 1) {
currentSeqSum += nums[i];
} else {
break;
}
}
longestSeqSum = currentSeqSum;
std::unordered_set<int> numSet(nums.begin(), nums.end());
for (int i = longestSeqSum; i <= 50; ++i) {
if (numSet.find(i) == numSet.end()) {
return i;
}
}
return longestSeqSum + 1;
}
int main() {
std::vector<int> nums = {3,4,5,1,12,14,13};
std::cout << smallest_missing_integer(nums);
return 0;
}function smallestMissingInteger(nums) {
let longestSeqSum = nums[0];
let currentSeqSum = nums[0];
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i - 1] + 1) {
currentSeqSum += nums[i];
} else {
break;
}
}
longestSeqSum = currentSeqSum;
const numSet = new Set(nums);
for (let i = longestSeqSum; i <= 50; i++) {
if (!numSet.has(i)) {
return i;
}
}
return longestSeqSum + 1;
}
const nums = [3, 4, 5, 1, 12, 14, 13];
console.log(smallestMissingInteger(nums));#include <stdio.h>
#include <stdbool.h>
int smallest_missing_integer(int* nums, int numsSize) {
int longestSeqSum = nums[0];
int currentSeqSum = nums[0];
for (int i = 1; i < numsSize; ++i) {
if (nums[i] == nums[i-1] + 1) {
currentSeqSum += nums[i];
} else {
break;
}
}
longestSeqSum = currentSeqSum;
for (int i = longestSeqSum; i <= 50; ++i) {
bool found = false;
for (int j = 0; j < numsSize; ++j) {
if (nums[j] == i) {
found = true;
break;
}
}
if (!found) {
return i;
}
}
return longestSeqSum + 1;
}
int main() {
int nums[] = {3,4,5,1,12,14,13};
int result = smallest_missing_integer(nums, sizeof(nums)/sizeof(nums[0]));
printf("%d", result);
return 0;
}using System;
using System.Collections.Generic;
public class SmallestMissingInteger {
public static int FindSmallestMissingInteger(int[] nums) {
int longestSeqSum = nums[0];
int currentSeqSum = nums[0];
for (int i = 1; i < nums.Length; i++) {
if (nums[i] == nums[i - 1] + 1) {
currentSeqSum += nums[i];
} else {
break;
}
}
longestSeqSum = currentSeqSum;
HashSet<int> numSet = new HashSet<int>(nums);
for (int i = longestSeqSum; i <= 50; i++) {
if (!numSet.Contains(i)) {
return i;
}
}
return longestSeqSum + 1;
}
public static void Main(string[] args) {
int[] nums = {3, 4, 5, 1, 12, 14, 13};
Console.WriteLine(FindSmallestMissingInteger(nums));
}
}The Python solution utilizes a set to check for missing integers efficiently and finds the smallest missing integer beginning from the sum of the longest sequential prefix.
Time Complexity: O(n), where n is the size of the array.
Space Complexity: O(n), due to the set storing elements of the array.
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.
def smallest_missing_integer(nums):
nums.sort()
longest_seq_sum = nums[0]
current_seq_sum = nums[0]
for i in range(1, len(nums)):
if nums[i] == nums[i - 1] + 1:
current_seq_sum += nums[i]
elif nums[i] > nums[i - 1] + 1:
break
longest_seq_sum = current_seq_sum
for i in range(longest_seq_sum, 51):
if i not in nums:
return i
return longest_seq_sum + 1
nums = [3, 4, 5, 1, 12, 14, 13]
print(smallest_missing_integer(nums))import java.util.Arrays;
public class SmallestMissingInteger {
public static int smallestMissingInteger(int[] nums) {
Arrays.sort(nums);
int longestSeqSum = nums[0];
int currentSeqSum = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1] + 1) {
currentSeqSum += nums[i];
} else if (nums[i] > nums[i - 1] + 1) {
break;
}
}
longestSeqSum = currentSeqSum;
for (int i = longestSeqSum; i <= 50; i++) {
if (Arrays.stream(nums).noneMatch(num -> num == i)) {
return i;
}
}
return longestSeqSum + 1;
}
public static void main(String[] args) {
int[] nums = {3, 4, 5, 1, 12, 14, 13};
System.out.println(smallestMissingInteger(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int smallest_missing_integer(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int longestSeqSum = nums[0];
int currentSeqSum = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
if (nums[i] == nums[i-1] + 1) {
currentSeqSum += nums[i];
} else if (nums[i] > nums[i-1] + 1) {
break;
}
}
longestSeqSum = currentSeqSum;
for (int i = longestSeqSum; i <= 50; ++i) {
if (std::find(nums.begin(), nums.end(), i) == nums.end()) {
return i;
}
}
return longestSeqSum + 1;
}
int main() {
std::vector<int> nums = {3,4,5,1,12,14,13};
std::cout << smallest_missing_integer(nums);
return 0;
}function smallestMissingInteger(nums) {
nums.sort((a, b) => a - b);
let longestSeqSum = nums[0];
let currentSeqSum = nums[0];
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i - 1] + 1) {
currentSeqSum += nums[i];
} else if (nums[i] > nums[i - 1] + 1) {
break;
}
}
longestSeqSum = currentSeqSum;
for (let i = longestSeqSum; i <= 50; i++) {
if (!nums.includes(i)) {
return i;
}
}
return longestSeqSum + 1;
}
const nums = [3, 4, 5, 1, 12, 14, 13];
console.log(smallestMissingInteger(nums));#include <stdio.h>
#include <stdbool.h>
int comparator(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int smallest_missing_integer(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), comparator);
int longestSeqSum = nums[0];
int currentSeqSum = nums[0];
for (int i = 1; i < numsSize; ++i) {
if (nums[i] == nums[i - 1] + 1) {
currentSeqSum += nums[i];
} else if (nums[i] > nums[i - 1] + 1) {
break;
}
}
longestSeqSum = currentSeqSum;
for (int i = longestSeqSum; i <= 50; ++i) {
bool found = false;
for (int j = 0; j < numsSize; ++j) {
if (nums[j] == i) {
found = true;
break;
}
}
if (!found) {
return i;
}
}
return longestSeqSum + 1;
}
int main() {
int nums[] = {3,4,5,1,12,14,13};
int result = smallest_missing_integer(nums, sizeof(nums)/sizeof(nums[0]));
printf("%d", result);
return 0;
}using System;
using System.Linq;
public class SmallestMissingInteger {
public static int FindSmallestMissingInteger(int[] nums) {
Array.Sort(nums);
int longestSeqSum = nums[0];
int currentSeqSum = nums[0];
for (int i = 1; i < nums.Length; i++) {
if (nums[i] == nums[i - 1] + 1) {
currentSeqSum += nums[i];
} else if (nums[i] > nums[i - 1] + 1) {
break;
}
}
longestSeqSum = currentSeqSum;
for (int i = longestSeqSum; i <= 50; i++) {
if (!nums.Contains(i)) {
return i;
}
}
return longestSeqSum + 1;
}
public static void Main(string[] args) {
int[] nums = {3, 4, 5, 1, 12, 14, 13};
Console.WriteLine(FindSmallestMissingInteger(nums));
}
}This Python solution simplifies sequence check via sorting, iterating to track the sequence sums and checking for smallest absent number in series form.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as space usage remains minimal through in-place operations.
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.
function missingInteger(nums: number[]): number {
let s = nums[0];
for (let j = 1; j < nums.length && nums[j] === nums[j - 1] + 1; ++j) {
s += nums[j];
}
const vis: Set<number> = new Set(nums);
for (let x = s; ; ++x) {
if (!vis.has(x)) {
return x;
}
}
}func missingInteger(nums []int) int {
s := nums[0]
for j := 1; j < len(nums) && nums[j] == nums[j-1]+1; j++ {
s += nums[j]
}
vis := [51]bool{}
for _, x := range nums {
vis[x] = true
}
for x := s; ; x++ {
if x >= len(vis) || !vis[x] {
return x
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Identify Longest Sequential Prefix and Check Missing Integer | Time Complexity: O(n), where n is the size of the array. |
| Approach 2: Tracking Sequence with a Sorted Array | Time Complexity: O(n log n) due to sorting. |
| Simulation + Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Identify Sequential Prefix + Hash Set Lookup | O(n) | O(n) | General case. Best performance with constant-time membership checks. |
| Sort Array and Scan for Missing Integer | O(n log n) | O(1) extra | When extra memory is limited and modifying the array is acceptable. |
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.