Jobs

Interviews

Discussions

Smallest Missing Integer Greater Than Sequential Prefix Sum

Easy

Asked by:

17 views

Topics:

Arrays

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.

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

Try coding it in LeetCode

Smallest Missing Integer Greater Than Sequential Prefix Sum

Easy

Asked by:

17 views

Topics:

Arrays

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.

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the input array? Could there be negative numbers, zero, or very large positive numbers?
If no missing integer greater than the sequential prefix sum exists, what should I return?
Can the input array be empty or null?
Are duplicate numbers allowed in the input array, and if so, how should they be handled regarding the prefix sums and the search for the smallest missing integer?
What data type should the returned missing integer be? Is it safe to assume it fits within the same integer range as the input array elements?

Brute Force Solution

Approach

The brute force approach to finding the smallest missing integer involves checking every possible integer, starting from 1, until we find one that meets the condition. For each potential integer, we need to verify if it's greater than the sum of any prefix of the input.

Here's how the algorithm would work step-by-step:

Start with the number 1.
Calculate the sum of the first number in the input.
See if the current number (starting with 1) is greater than the sum we just calculated.
If it's not, calculate the sum of the first two numbers in the input.
Again, see if our current number is greater than this new sum.
Keep calculating the sum of longer and longer prefixes of the input and comparing it to our current number. Stop once you reach the entire input length.
If at any point, the current number is less than or equal to the sum of a prefix, move on to the next number and repeat the process, starting from the beginning (calculating sum of the first input number and so on).
If the current number is greater than the sum of *every* possible prefix, then you have found the smallest missing integer, and you can stop.

Code Implementation

def find_smallest_missing_integer(numbers):
    potential_missing_integer = 1

    while True:
        is_missing = True
        prefix_sum = 0

        # Iterate through prefixes to see if the number is missing
        for index in range(len(numbers)): 
            prefix_sum += numbers[index]

            # Number not missing if less than or equal to prefix sum
            if potential_missing_integer <= prefix_sum:
                is_missing = False
                break

        # If it is missing return the integer
        if is_missing:
            return potential_missing_integer
        else:
            potential_missing_integer += 1

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through potential missing integers, starting from 1. For each potential integer, it calculates prefix sums of the input array. In the worst case, we may need to check up to n potential integers. For each integer, we calculate at most n prefix sums by iterating through the input array. Therefore, the total number of operations is proportional to n * n. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The provided algorithm primarily uses a single variable to store the potential smallest missing integer and another to accumulate the prefix sums. No auxiliary data structures like arrays, hash maps, or lists are created to store intermediate values derived from the input. Therefore, the space used remains constant irrespective of the input size N, resulting in a space complexity of O(1).

Optimal Solution

Approach

The goal is to find the smallest positive number missing from the given numbers but with a special twist involving prefix sums. We need to keep track of the running sum of the numbers and make sure the number we return is larger than that sum.

Here's how the algorithm would work step-by-step:

First, create a container to hold the positive numbers that appear in our given set of numbers.
Next, compute a running sum of the numbers in the set.
At each step, check the container of positive numbers to see if the number one greater than the running sum already exists. If it doesn't, we've found our answer.
If a number one greater than the running sum exists, add to the running sum and continue down the list of numbers.
If you reach the end of the list, the result is one greater than the final running sum.

Code Implementation

def find_smallest_missing(
    numbers):
    positive_numbers = set()
    for number in numbers:
        if number > 0:
            positive_numbers.add(number)

    running_sum = 0

    for number in numbers:
        #Check if number > running sum exists
        if (running_sum + 1) not in positive_numbers:
            return running_sum + 1

        # Advance the running sum
        running_sum += number

    # If loop completes, result is running_sum + 1
    return running_sum + 1

Big(O) Analysis

Time Complexity

O(n) – Creating the container of positive numbers involves iterating through the input array of size n, which takes O(n) time. The subsequent loop calculates the running sum and checks for the existence of the next expected number within the positive numbers container. Checking for existence can be considered O(1) with an appropriate data structure like a set or hash table. Therefore, the loop also iterates up to n times, performing constant-time operations within each iteration. The dominant factor is iterating the input array, resulting in an overall time complexity of O(n).

Space Complexity

O(N) – The algorithm uses a container to hold positive numbers from the input array. In the worst case, all N input numbers are positive and unique, requiring storage for all of them. This container (likely a set or hash map) therefore occupies space proportional to the number of positive elements, up to N. Thus the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 1 immediately as the prefix sum is 0, and the smallest missing positive integer greater than 0 is 1.
Array contains only negative numbers	Return 1 as all prefix sums will be negative and the smallest missing positive integer is 1.
Array contains only positive numbers where the sum is always increasing	Iterate through the array; the result will be one greater than the largest prefix sum if no missing number is found during iteration.
Array contains zeros	Zeros will not affect prefix sum calculations if they are non-sequential and they don't introduce new possible results.
Array contains a large number of elements causing integer overflow in prefix sum calculations	Use a language with arbitrary-precision integers or use a data type that can accommodate very large numbers (e.g., long) and handle potential overflow exceptions.
The smallest missing integer is greater than the maximum possible integer value	The problem should explicitly define a constraint on maximum possible value, otherwise the algorithm should eventually return with no solution.
All positive integers from 1 to N are present in the prefix sums	Return N+1 as the smallest missing integer.
Array containing very large positive numbers followed by large negative numbers that brings the sum back to small values	The solution must correctly track the largest prefix sum at each index and compare it against all positive numbers encountered so far; this requires tracking both prefix sums and the set of present positive integers.

Empty input array

How to Handle:

Return 1 immediately as the prefix sum is 0, and the smallest missing positive integer greater than 0 is 1.

Array contains only negative numbers

How to Handle:

Return 1 as all prefix sums will be negative and the smallest missing positive integer is 1.

Array contains only positive numbers where the sum is always increasing

How to Handle:

Iterate through the array; the result will be one greater than the largest prefix sum if no missing number is found during iteration.

Array contains zeros

How to Handle:

Zeros will not affect prefix sum calculations if they are non-sequential and they don't introduce new possible results.

Array contains a large number of elements causing integer overflow in prefix sum calculations

How to Handle:

Use a language with arbitrary-precision integers or use a data type that can accommodate very large numbers (e.g., long) and handle potential overflow exceptions.

The smallest missing integer is greater than the maximum possible integer value

How to Handle:

The problem should explicitly define a constraint on maximum possible value, otherwise the algorithm should eventually return with no solution.

All positive integers from 1 to N are present in the prefix sums

How to Handle:

Return N+1 as the smallest missing integer.

Array containing very large positive numbers followed by large negative numbers that brings the sum back to small values

How to Handle:

The solution must correctly track the largest prefix sum at each index and compare it against all positive numbers encountered so far; this requires tracking both prefix sums and the set of present positive integers.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the input array? Could there be negative numbers, zero, or very large positive numbers?
If no missing integer greater than the sequential prefix sum exists, what should I return?
Can the input array be empty or null?
Are duplicate numbers allowed in the input array, and if so, how should they be handled regarding the prefix sums and the search for the smallest missing integer?
What data type should the returned missing integer be? Is it safe to assume it fits within the same integer range as the input array elements?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the number 1.
Calculate the sum of the first number in the input.
See if the current number (starting with 1) is greater than the sum we just calculated.
If it's not, calculate the sum of the first two numbers in the input.
Again, see if our current number is greater than this new sum.
Keep calculating the sum of longer and longer prefixes of the input and comparing it to our current number. Stop once you reach the entire input length.
If at any point, the current number is less than or equal to the sum of a prefix, move on to the next number and repeat the process, starting from the beginning (calculating sum of the first input number and so on).
If the current number is greater than the sum of *every* possible prefix, then you have found the smallest missing integer, and you can stop.

Code Implementation

def find_smallest_missing_integer(numbers):
    potential_missing_integer = 1

    while True:
        is_missing = True
        prefix_sum = 0

        # Iterate through prefixes to see if the number is missing
        for index in range(len(numbers)): 
            prefix_sum += numbers[index]

            # Number not missing if less than or equal to prefix sum
            if potential_missing_integer <= prefix_sum:
                is_missing = False
                break

        # If it is missing return the integer
        if is_missing:
            return potential_missing_integer
        else:
            potential_missing_integer += 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a container to hold the positive numbers that appear in our given set of numbers.
Next, compute a running sum of the numbers in the set.
At each step, check the container of positive numbers to see if the number one greater than the running sum already exists. If it doesn't, we've found our answer.
If a number one greater than the running sum exists, add to the running sum and continue down the list of numbers.
If you reach the end of the list, the result is one greater than the final running sum.

Code Implementation

def find_smallest_missing(
    numbers):
    positive_numbers = set()
    for number in numbers:
        if number > 0:
            positive_numbers.add(number)

    running_sum = 0

    for number in numbers:
        #Check if number > running sum exists
        if (running_sum + 1) not in positive_numbers:
            return running_sum + 1

        # Advance the running sum
        running_sum += number

    # If loop completes, result is running_sum + 1
    return running_sum + 1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 1 immediately as the prefix sum is 0, and the smallest missing positive integer greater than 0 is 1.
Array contains only negative numbers	Return 1 as all prefix sums will be negative and the smallest missing positive integer is 1.
Array contains only positive numbers where the sum is always increasing	Iterate through the array; the result will be one greater than the largest prefix sum if no missing number is found during iteration.
Array contains zeros	Zeros will not affect prefix sum calculations if they are non-sequential and they don't introduce new possible results.
Array contains a large number of elements causing integer overflow in prefix sum calculations	Use a language with arbitrary-precision integers or use a data type that can accommodate very large numbers (e.g., long) and handle potential overflow exceptions.
The smallest missing integer is greater than the maximum possible integer value	The problem should explicitly define a constraint on maximum possible value, otherwise the algorithm should eventually return with no solution.
All positive integers from 1 to N are present in the prefix sums	Return N+1 as the smallest missing integer.
Array containing very large positive numbers followed by large negative numbers that brings the sum back to small values	The solution must correctly track the largest prefix sum at each index and compare it against all positive numbers encountered so far; this requires tracking both prefix sums and the set of present positive integers.

Empty input array

How to Handle:

Return 1 immediately as the prefix sum is 0, and the smallest missing positive integer greater than 0 is 1.

Array contains only negative numbers

How to Handle:

Return 1 as all prefix sums will be negative and the smallest missing positive integer is 1.

Array contains only positive numbers where the sum is always increasing

How to Handle:

Iterate through the array; the result will be one greater than the largest prefix sum if no missing number is found during iteration.

Array contains zeros

How to Handle:

Zeros will not affect prefix sum calculations if they are non-sequential and they don't introduce new possible results.

Array contains a large number of elements causing integer overflow in prefix sum calculations

How to Handle:

Use a language with arbitrary-precision integers or use a data type that can accommodate very large numbers (e.g., long) and handle potential overflow exceptions.

The smallest missing integer is greater than the maximum possible integer value

How to Handle:

The problem should explicitly define a constraint on maximum possible value, otherwise the algorithm should eventually return with no solution.

All positive integers from 1 to N are present in the prefix sums

How to Handle:

Return N+1 as the smallest missing integer.

Array containing very large positive numbers followed by large negative numbers that brings the sum back to small values

How to Handle: