We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest Missing Integer Greater Than Sequential Prefix Sum

Difficulty: Easy

Problem Description

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.

Key Insights

  • Identify the longest sequential prefix in the array.
  • Calculate the sum of this sequential prefix.
  • Determine the smallest integer greater than or equal to this sum that is missing from the array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can follow these steps:

  1. Iterate through the array to find the longest sequential prefix, maintaining a sum of this prefix.
  2. Use a set to store all the elements in the array for O(1) average time complexity lookup.
  3. Starting from the sum of the longest sequential prefix, check for the smallest integer that is missing from the set.

We utilize a list or array to track numbers and a set for quick existence checks.

Code Solutions

def smallest_missing_integer(nums):
    longest_sum = 0
    current_sum = 0
    longest_length = 0

    for i in range(len(nums)):
        if i == 0 or nums[i] == nums[i - 1] + 1:
            current_sum += nums[i]
            longest_length += 1
        else:
            break
    
    longest_sum = current_sum
    num_set = set(nums)
    
    # Find the smallest missing integer >= longest_sum
    x = longest_sum
    while x in num_set:
        x += 1
        
    return x
← Back to All Questions