Smallest Missing Integer Greater Than Sequential Prefix Sum — LeetCode 2996 Python Solution
EasyArrayHash TableSorting
- Problem
- #2996
- Pattern
- Sorting
- Reading time
- 2 min
- Source
- leetcode.com
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.
Example
- 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.
Python solution
Python
class Solution:
def missingInteger(self, nums: List[int]) -> int:
s, j = nums[0], 1
while j < len(nums) and nums[j] == nums[j - 1] + 1:
s += nums[j]
j += 1
vis = set(nums)
for x in count(s):
if x not in vis:
return xComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n), where n is the length of the array nums auxiliary |
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 2996. Smallest Missing Integer Greater Than Sequential Prefix Sum is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2996. Smallest Missing Integer Greater Than Sequential Prefix Sum?
- LeetCode 2996. Smallest Missing Integer Greater Than Sequential Prefix Sum is rated Easy on LeetCode.
- What is the time complexity of LeetCode 2996. Smallest Missing Integer Greater Than Sequential Prefix Sum?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2996. Smallest Missing Integer Greater Than Sequential Prefix Sum?
- The Python solution on this page uses O(n), where n is the length of the array nums auxiliary space.
- What topics does LeetCode 2996. Smallest Missing Integer Greater Than Sequential Prefix Sum cover?
- LeetCode 2996. Smallest Missing Integer Greater Than Sequential Prefix Sum is tagged Array, Hash Table and Sorting on LeetCode.