Smallest Missing Integer Greater Than Sequential Prefix Sum Solution
Smallest Missing Integer Greater Than Sequential Prefix Sum solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Smallest Missing Integer Greater Than Sequential Prefix Sum is an easy coding problem on arrays, hash table and sorting, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A prefix nums[0..i] is sequential if every element after the first is exactly one more than the element before it (nums[j] = nums[j - 1] + 1 for 1 <= j <= i). The prefix holding only nums[0] is always sequential.
Let s be the sum of the longest sequential prefix of nums. Return the smallest integer x that is missing from nums and satisfies x >= s.
Example 1
Input: nums = [1,2,3,2,5]
Output: 6
Explanation: The longest sequential prefix is `[1,2,3]` with sum 6, and 6 is not in `nums`.
Example 2
Input: nums = [3,4,5,1,12,14,13]
Output: 15
Explanation: The prefix `[3,4,5]` sums to 12; 12, 13 and 14 all occur, so the answer is 15.
Example 3
Input: nums = [5]
Output: 6
Explanation: The sum is 5, which is in the array.
Constraints
1 <= nums.length <= 501 <= nums[i] <= 50
Hints for Smallest Missing Integer Greater Than Sequential Prefix Sum
Hint 1
First walk the prefix while each element is one more than the previous, summing as you go.
Hint 2
Then start from that sum and step upwards until you reach a value not in the array.
Hint 3
A set (or a boolean table — values are at most 50) makes each membership test O(1).
How to solve Smallest Missing Integer Greater Than Sequential Prefix Sum
Two plain passes: sum the longest run nums[0], nums[0] + 1, … at the start, then probe upward from that sum against a set of the array's values.
Approach
- Set
s = nums[0]; fori = 1, 2, …whilenums[i] == nums[i - 1] + 1, addnums[i]tos. - Put every element of
numsinto a set. - While
sis in the set, increments. Returns.
Why it works
The first loop stops at the first break in the sequence, which is exactly the end of the longest sequential prefix. The second loop tries candidates in increasing order starting from s, so the first one missing from the set is the smallest valid x; it terminates within n + 1 steps because the array has only n values.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The prefix must start at index 0 — a longer consecutive run later in the array does not count.
xmay equalsitself; the condition isx >= s, notx > s.
Reference solution
Python
from typing import List
def missingInteger(nums: List[int]) -> int:
s = nums[0]
i = 1
while i < len(nums) and nums[i] == nums[i - 1] + 1:
s += nums[i]
i += 1
present = set(nums)
while s in present:
s += 1
return sJava
public static int missingInteger(int[] nums) {
int s = nums[0];
for (int i = 1; i < nums.length && nums[i] == nums[i - 1] + 1; i++) s += nums[i];
HashSet<Integer> present = new HashSet<>();
for (int v : nums) present.add(v);
while (present.contains(s)) s++;
return s;
}C++
int missingInteger(vector<int>& nums) {
int s = nums[0];
for (size_t i = 1; i < nums.size() && nums[i] == nums[i - 1] + 1; i++) s += nums[i];
unordered_set<int> present(nums.begin(), nums.end());
while (present.count(s)) s++;
return s;
}JavaScript
var missingInteger = function(nums) {
var s = nums[0];
for (var i = 1; i < nums.length && nums[i] === nums[i - 1] + 1; i++) s += nums[i];
var present = new Set(nums);
while (present.has(s)) s++;
return s;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets