Smallest missing integer greater than sequential prefix sum

Array Hash Table Sorting

35.1% acceptance

Feb 25, 2026

175

310

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn missing_integer(nums: Vec<i32>) -> i32 {
    use std::collections::HashSet;

    // Find sum of longest sequential prefix
    let mut sum = nums[0];
    for i in 1..nums.len() {
      if nums[i] == nums[i - 1] + 1 {
        sum += nums[i];
      } else {
        break;
      }
    }

    let set: HashSet<i32> = nums.iter().cloned().collect();
    let mut x = sum;
    while set.contains(&x) {
      x += 1;
    }
    x
  }
}