Smallest Missing Integer Greater Than Sequential Prefix Sum

Easy
1811.

Smallest Missing Integer Greater Than Sequential Prefix Sum

Smallest Missing Integer Greater Than Sequential Prefix Sum is an easy coding problem on arrays, hash table and sorting, asked in Amazon interviews.

A prefix nums[0..i] is sequential if every element after the first is exactly one more than the element before it (nums[j] = nums[j - 1] + 1 for 1 <= j <= i). The prefix holding only nums[0] is always sequential.

Let s be the sum of the longest sequential prefix of nums. Return the smallest integer x that is missing from nums and satisfies x >= s.

Example 1

Input
nums = [1,2,3,2,5]
Output
6
Explanation
The longest sequential prefix is `[1,2,3]` with sum 6, and 6 is not in `nums`.

Example 2

Input
nums = [3,4,5,1,12,14,13]
Output
15
Explanation
The prefix `[3,4,5]` sums to 12; 12, 13 and 14 all occur, so the answer is 15.

Example 3

Input
nums = [5]
Output
6
Explanation
The sum is 5, which is in the array.

Constraints

  • 1 <= nums.length <= 50
  • 1 <= nums[i] <= 50
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var missingInteger = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Smallest Missing Integer Greater Than Sequential Prefix Sum Solution

Smallest Missing Integer Greater Than Sequential Prefix Sum solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Smallest Missing Integer Greater Than Sequential Prefix Sum is an easy coding problem on arrays, hash table and sorting, asked in Amazon interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table, Sorting
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A prefix nums[0..i] is sequential if every element after the first is exactly one more than the element before it (nums[j] = nums[j - 1] + 1 for 1 <= j <= i). The prefix holding only nums[0] is always sequential.

Let s be the sum of the longest sequential prefix of nums. Return the smallest integer x that is missing from nums and satisfies x >= s.

Example 1

Input: nums = [1,2,3,2,5]
Output: 6
Explanation: The longest sequential prefix is `[1,2,3]` with sum 6, and 6 is not in `nums`.

Example 2

Input: nums = [3,4,5,1,12,14,13]
Output: 15
Explanation: The prefix `[3,4,5]` sums to 12; 12, 13 and 14 all occur, so the answer is 15.

Example 3

Input: nums = [5]
Output: 6
Explanation: The sum is 5, which is in the array.

Constraints

  • 1 <= nums.length <= 50
  • 1 <= nums[i] <= 50

Hints for Smallest Missing Integer Greater Than Sequential Prefix Sum

  1. Hint 1

    First walk the prefix while each element is one more than the previous, summing as you go.

  2. Hint 2

    Then start from that sum and step upwards until you reach a value not in the array.

  3. Hint 3

    A set (or a boolean table — values are at most 50) makes each membership test O(1).

How to solve Smallest Missing Integer Greater Than Sequential Prefix Sum

Two plain passes: sum the longest run nums[0], nums[0] + 1, … at the start, then probe upward from that sum against a set of the array's values.

Approach

  1. Set s = nums[0]; for i = 1, 2, … while nums[i] == nums[i - 1] + 1, add nums[i] to s.
  2. Put every element of nums into a set.
  3. While s is in the set, increment s. Return s.

Why it works

The first loop stops at the first break in the sequence, which is exactly the end of the longest sequential prefix. The second loop tries candidates in increasing order starting from s, so the first one missing from the set is the smallest valid x; it terminates within n + 1 steps because the array has only n values.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The prefix must start at index 0 — a longer consecutive run later in the array does not count.
  • x may equal s itself; the condition is x >= s, not x > s.

Reference solution

Python

from typing import List

def missingInteger(nums: List[int]) -> int:
    s = nums[0]
    i = 1
    while i < len(nums) and nums[i] == nums[i - 1] + 1:
        s += nums[i]
        i += 1
    present = set(nums)
    while s in present:
        s += 1
    return s

Java

public static int missingInteger(int[] nums) {
    int s = nums[0];
    for (int i = 1; i < nums.length && nums[i] == nums[i - 1] + 1; i++) s += nums[i];
    HashSet<Integer> present = new HashSet<>();
    for (int v : nums) present.add(v);
    while (present.contains(s)) s++;
    return s;
}

C++

int missingInteger(vector<int>& nums) {
    int s = nums[0];
    for (size_t i = 1; i < nums.size() && nums[i] == nums[i - 1] + 1; i++) s += nums[i];
    unordered_set<int> present(nums.begin(), nums.end());
    while (present.count(s)) s++;
    return s;
}

JavaScript

var missingInteger = function(nums) {
    var s = nums[0];
    for (var i = 1; i < nums.length && nums[i] === nums[i - 1] + 1; i++) s += nums[i];
    var present = new Set(nums);
    while (present.has(s)) s++;
    return s;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets