Smallest Missing Integer Greater Than Sequential Prefix Sum

Difficulty: Easy | Acceptance: 35.40% | Paid: No Topics: Array, Hash Table, Sorting

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

A prefix nums[0..i] is sequential if, for every element j in the range [1, i], nums[j] = nums[j - 1] + 1. In other words, each element is exactly one more than the previous element.

Return the smallest missing integer greater than the sum of the longest sequential prefix of nums.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Hash Set
• Approach 3: Sorting

Examples

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 1: Brute Force

Intuition First, calculate the sum of the longest sequential prefix. Then, iterate starting from sum + 1 and check if each number exists in the array using a linear search.

Steps

• Iterate through nums to find the longest sequential prefix and calculate its sum.
• Initialize missing to sum + 1.
• While missing is found in nums (using a loop), increment missing.
• Return missing.

class Solution:
    def missingInteger(self, nums: list[int]) -> int:
        prefix_sum = nums[0]
        i = 1
        while i < len(nums) and nums[i] == nums[i-1] + 1:
            prefix_sum += nums[i]
            i += 1
        
        missing = prefix_sum + 1
        while True:
            found = False
            for num in nums:
                if num == missing:
                    found = True
                    break
            if not found:
                return missing
            missing += 1

Complexity

• Time: O(n²) in the worst case, where n is the length of nums.
• Space: O(1)
• Notes: Simple to implement but inefficient for large arrays due to repeated linear scans.

Approach 2: Hash Set

Intuition Optimize the lookup process by storing all elements of nums in a Hash Set. This allows O(1) average time complexity for checking the existence of a number.

Steps

• Calculate the sum of the longest sequential prefix.
• Store all elements of nums in a set.
• Initialize missing to sum + 1.
• While missing is present in the set, increment missing.
• Return missing.

class Solution:
    def missingInteger(self, nums: list[int]) -> int:
        prefix_sum = nums[0]
        i = 1
        while i < len(nums) and nums[i] == nums[i-1] + 1:
            prefix_sum += nums[i]
            i += 1
        
        num_set = set(nums)
        missing = prefix_sum + 1
        while missing in num_set:
            missing += 1
        return missing

Complexity

• Time: O(n) on average, where n is the length of nums.
• Space: O(n) to store the set.
• Notes: This is the most optimal approach for general cases, trading space for time.

Approach 3: Sorting

Intuition Sort the array to easily identify the smallest missing integer. After sorting, we can iterate through the array to find the first gap greater than the prefix sum.

Steps

• Calculate the sum of the longest sequential prefix.
• Sort a copy of the array.
• Iterate through the sorted array. If we encounter a number equal to target (starting from sum + 1), increment target. If we encounter a number greater than target, we have found the missing integer.
• Return target.

class Solution:
    def missingInteger(self, nums: list[int]) -> int:
        prefix_sum = nums[0]
        i = 1
        while i < len(nums) and nums[i] == nums[i-1] + 1:
            prefix_sum += nums[i]
            i += 1
        
        sorted_nums = sorted(nums)
        target = prefix_sum + 1
        for num in sorted_nums:
            if num == target:
                target += 1
            elif num > target:
                break
        return target

Complexity

• Time: O(n log n) due to the sorting step.
• Space: O(n) if we create a copy of the array, or O(1) if we sort in-place (though modifying input is generally discouraged).
• Notes: Useful if the array is already sorted or if memory is extremely constrained (in-place sort).