Smallest Missing Integer Greater Than Sequential Prefix Sum

EASY

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.

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

Approaches

Checkout 3 different approaches to solve Smallest Missing Integer Greater Than Sequential Prefix Sum. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Search

This approach first calculates the sum of the longest sequential prefix. Then, it iteratively checks for the smallest integer, starting from the calculated sum, that is not present in the input array. The check for presence is done by linearly scanning the entire array for each candidate integer.

Algorithm

Calculate Prefix Sum: Initialize prefixSum = nums[0]. Iterate from i = 1 to n-1. If nums[i] == nums[i-1] + 1, add nums[i] to prefixSum. Otherwise, break the loop.
Iterative Search: Initialize a candidate integer x with the value of prefixSum.
Start a while(true) loop.
Inside the loop, check if x exists in the nums array by iterating through nums from start to end.
If x is found, increment x and continue to the next iteration.
If x is not found after checking all elements, it is the smallest missing integer. Return x.

The method involves two main steps. First, we determine the longest sequential prefix and compute its sum. We start with the first element as the initial sum and iterate from the second element. As long as the current element is one greater than the previous, we extend the sequential prefix and add the current element to our running sum. We stop as soon as this condition is violated.

Second, we find the smallest integer x that is greater than or equal to the computed sum and is not present in the nums array. We start by setting our candidate x to the sum. We then enter a loop. In each iteration, we perform a linear scan through the nums array to see if x is present. If it is, we increment x and repeat the scan. If we complete a scan without finding x, we have found our answer, and we return x.

class Solution {
    public int missingInteger(int[] nums) {
        // Step 1: Calculate the sum of the longest sequential prefix
        long prefixSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] + 1) {
                prefixSum += nums[i];
            } else {
                break;
            }
        }

        // Step 2: Find the smallest missing integer >= prefixSum
        int x = (int) prefixSum;
        while (true) {
            boolean found = false;
            for (int num : nums) {
                if (num == x) {
                    found = true;
                    break;
                }
            }
            if (found) {
                x++;
            } else {
                return x;
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the number of elements in `nums`. Calculating the prefix sum takes O(N). The search for the missing integer involves a loop that can run up to N+1 times in the worst case, and inside this loop, we scan the array again, which takes O(N). This results in a total complexity of O(N + N*N) = O(N^2).Space Complexity: O(1), as we only use a few variables to store the sum and the candidate integer, regardless of the input size.

Pros and Cons

Pros:

Simple to understand and implement.
Space-efficient, as it uses O(1) extra space.

Cons:

The time complexity is quadratic, O(N^2), which is inefficient for larger inputs.
It repeatedly scans the input array, which is redundant.

Code Solutions

Checking out 3 solutions in different languages for Smallest Missing Integer Greater Than Sequential Prefix Sum. Click on different languages to view the code.

class Solution { public int missingInteger ( int [] nums ) { int s = nums [ 0 ]; for ( int j = 1 ; j < nums . length && nums [ j ] == nums [ j - 1 ] + 1 ; ++ j ) { s += nums [ j ]; } boolean [] vis = new boolean [ 51 ]; for ( int x : nums ) { vis [ x ] = true ; } for ( int x = s ;; ++ x ) { if ( x >= vis . length || ! vis [ x ]) { return x ; } } } }

Video Solution

Watch the video walkthrough for Smallest Missing Integer Greater Than Sequential Prefix Sum

Algorithms:

Sorting

Data Structures:

ArrayHash Table