Skip to content

2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

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

Solutions

Solution 1: Simulation

Thinking

The longest sequential prefix starts at index \(0\); let \(s\) be its sum. We want the least integer \(\ge s\) absent from the array. \(n \le 50\): scan the prefix sum, then test \(s,s+1,\ldots\) against a set.

The domain is tiny, so a linear increment hits the gap.

First, we calculate the sum \(s\) of the longest sequential prefix of the array \(nums\). Then, starting from \(s\), we enumerate the integer \(x\). If \(x\) is not in the array \(nums\), then \(x\) is the answer.

Since \(nums[i] \leq 50\) in this problem, we can use an array of length \(51\) (or a hash table) to record the integers that appear in the array, so as to quickly determine whether an integer is in the array \(nums\).

The time complexity is \(O(n + M)\), and the space complexity is \(O(M)\). Where \(n\) is the length of the array \(nums\), and \(M\) is the upper bound of the array elements, which is \(51\) in this problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        s = nums[0]
        for x, y in pairwise(nums):
            if x + 1 != y:
                break
            s += y
        st = set(nums)
        while s in st:
            s += 1
        return s

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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];
        }
        final int m = 51;
        boolean[] st = new boolean[m];
        for (int x : nums) {
            st[x] = true;
        }
        while (s < m && st[s]) {
            ++s;
        }
        return s;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int missingInteger(vector<int>& nums) {
        int s = nums[0];
        for (int j = 1; j < nums.size() && nums[j] == nums[j - 1] + 1; ++j) {
            s += nums[j];
        }

        const int m = 51;
        bool st[m] = {};
        for (int x : nums) {
            st[x] = true;
        }

        while (s < m && st[s]) {
            ++s;
        }
        return s;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func missingInteger(nums []int) int {
    s := nums[0]
    for j := 1; j < len(nums) && nums[j] == nums[j-1]+1; j++ {
        s += nums[j]
    }

    const m = 51
    st := make([]bool, m)
    for _, x := range nums {
        st[x] = true
    }

    for s < m && st[s] {
        s++
    }
    return s
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function missingInteger(nums: number[]): number {
    let s = nums[0];
    for (let j = 1; j < nums.length && nums[j] === nums[j - 1] + 1; ++j) {
        s += nums[j];
    }

    const m = 51;
    const st = new Array<boolean>(m).fill(false);
    for (const x of nums) {
        st[x] = true;
    }

    while (s < m && st[s]) {
        ++s;
    }
    return s;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
impl Solution {
    pub fn missing_integer(nums: Vec<i32>) -> i32 {
        let mut s = nums[0];

        for j in 1..nums.len() {
            if nums[j] != nums[j - 1] + 1 {
                break;
            }
            s += nums[j];
        }

        const M: usize = 51;
        let mut st = [false; M];

        for &x in &nums {
            st[x as usize] = true;
        }

        while s < M as i32 && st[s as usize] {
            s += 1;
        }

        s
    }
}

Comments