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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Missing Integer Greater Than Sequential Prefix Sum

Number: 3236

Difficulty: Easy

Paid? No

Companies: Meta, Microsoft

Problem Description

Given a 0-indexed integer array nums, determine the longest sequential prefix of nums (a prefix is sequential if every element from index 1 onward is exactly one greater than its previous element). Compute the sum of this prefix and then return the smallest integer x that is not present in nums and is greater than or equal to this sum.

Key Insights

  • Identify the longest sequential prefix by iterating from the beginning and checking if nums[j] equals nums[j-1] + 1.
  • Compute the sum of this sequential prefix.
  • Use a hash set (or equivalent) to store all numbers from nums for O(1) membership lookup.
  • Starting from the prefix sum, incrementally search for the first integer that does not exist in the set.

Space and Time Complexity

Time Complexity: O(n + k) where n is the length of nums and k is the number of increments needed to find the missing integer (both are small given the constraints).
Space Complexity: O(n) due to storing nums in a hash set for fast lookups.

Solution

The solution involves:

  1. Iterating over the array to build the longest sequential prefix.
  2. Calculating the sum of this prefix.
  3. Using a hash set for quick membership checks.
  4. Starting at the prefix sum, incrementing until we find an integer that is not in the hash set. This approach guarantees that we find the smallest missing integer greater than or equal to the sum of the sequential prefix.

Code Solutions

def smallest_missing(nums):
    # Ensure the list is non-empty (per constraints, it is at least length 1)
    prefix = [nums[0]]
    # Build the longest sequential prefix from the start
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1] + 1:
            prefix.append(nums[i])
        else:
            break
    # Calculate the sum of the sequential prefix
    prefix_sum = sum(prefix)
    # Create a set from nums for O(1) lookups
    num_set = set(nums)
    # Find the smallest missing integer starting from prefix_sum
    x = prefix_sum
    while x in num_set:
        x += 1
    return x

# Example usage:
print(smallest_missing([1,2,3,2,5]))       # Expected output: 6
print(smallest_missing([3,4,5,1,12,14,13])) # Expected output: 15
← Back to All Questions