Smallest Missing Integer Greater Than Sequential Prefix Sum
EasyPrompt
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 <= 501 <= nums[i] <= 50
Approaches
3 approaches with complexity analysis and trade-offs.
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 fromi = 1ton-1. Ifnums[i] == nums[i-1] + 1, addnums[i]toprefixSum. Otherwise, break the loop. - Iterative Search: Initialize a candidate integer
xwith the value ofprefixSum. - Start a
while(true)loop. - Inside the loop, check if
xexists in thenumsarray by iterating throughnumsfrom start to end. - If
xis found, incrementxand continue to the next iteration. - If
xis not found after checking all elements, it is the smallest missing integer. Returnx.
Walkthrough
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
Time
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
O(1), as we only use a few variables to store the sum and the candidate integer, regardless of the input size.
Trade-offs
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.
This approach improves upon the brute-force method by optimizing the search for the missing integer. After calculating the prefix sum, it first stores all elements of the input array into a HashSet. This allows for checking the existence of an integer in average O(1) time, significantly speeding up the search process.
Algorithm
- Calculate Prefix Sum: This step is the same as the brute-force approach. Find the sum of the longest sequential prefix.
- Populate HashSet: Create a
HashSet<Integer>and add all elements from thenumsarray into it. This allows for O(1) average time complexity for checking the existence of an element. - Optimized Search: Initialize a candidate integer
xwith the value ofprefixSum. - Use a
whileloop that continues as long asset.contains(x)is true. - Inside the loop, increment
x. - When the loop terminates,
xis the first integer not found in the set, so returnx.
Walkthrough
This method enhances the previous one by trading space for time. The first step, calculating the sum of the longest sequential prefix, remains unchanged.
Next, to accelerate the search for the missing number, we first populate a HashSet with all the elements from the nums array. This preprocessing step takes O(N) time but allows subsequent existence checks (contains operations) to be performed in average O(1) time.
Finally, we initialize our candidate integer x to the calculated prefix sum. We then repeatedly check if x is in our HashSet. As long as it is, we increment x. The first value of x that is not found in the set is our answer.
import java.util.HashSet;import java.util.Set; 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: Store all numbers in a HashSet for O(1) lookup Set<Integer> numSet = new HashSet<>(); for (int num : nums) { numSet.add(num); } // Step 3: Find the smallest missing integer >= prefixSum int x = (int) prefixSum; while (numSet.contains(x)) { x++; } return x; }}Complexity
Time
O(N). Calculating the prefix sum is O(N). Populating the `HashSet` is O(N). The final search loop runs at most N+1 times, with each check being an O(1) operation on average. Thus, the total time complexity is O(N).
Space
O(N), where N is the number of elements in `nums`. This space is used to store the elements in the `HashSet`.
Trade-offs
Pros
Much more time-efficient than the brute-force approach, with a linear time complexity of O(N).
The logic remains relatively simple.
Cons
Requires extra space proportional to the number of elements in the input array, O(N).
This is the most efficient approach, leveraging the problem's constraints on the values within the nums array (1 <= nums[i] <= 50). Instead of a HashSet, it uses a boolean array as a direct address table (or frequency map) to track the presence of numbers. This provides O(1) lookup time like a HashSet but with constant space complexity, as the array size is fixed by the constraints and does not depend on the input size N.
Algorithm
- Calculate Prefix Sum: Same as the previous approaches.
- Create Boolean Presence Array: Create a boolean array, e.g.,
presentof size 51, since1 <= nums[i] <= 50. Initialize it to allfalse. - Mark Present Numbers: Iterate through
nums. For eachnum, ifnum <= 50, setpresent[num] = true. - Efficient Search: Initialize
xwithprefixSum. - Use a
whileloop:while (x <= 50 && present[x]). - Inside the loop, increment
x. - After the loop,
xis the answer. Ifxbecame greater than 50, it's guaranteed to be missing. If it's less than or equal to 50, it's the first number not marked as present.
Walkthrough
This approach is the most optimized, taking full advantage of the problem's constraints. The first step of calculating the prefix sum is the same.
The key optimization is in how we check for the presence of numbers. Since all numbers in nums are between 1 and 50, we can use a simple boolean array of size 51 as a direct mapping. We create boolean[] present = new boolean[51] and iterate through nums, setting present[num] = true for each number num in the input.
With this present array, checking for a number's existence is an O(1) operation. We initialize our candidate x to the prefix sum. We then increment x as long as it is within the bounds of our present array (i.e., x <= 50) and is marked as present (present[x] is true). The loop stops when x is a number not present in nums or when x exceeds 50. In either case, this final value of x is the smallest missing integer we are looking for, because any number greater than 50 is guaranteed not to be in the original nums array.
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: Mark numbers present in the input array boolean[] present = new boolean[51]; for (int num : nums) { if (num <= 50) { present[num] = true; } } // Step 3: Find the smallest missing integer >= prefixSum int x = (int) prefixSum; while (x <= 50 && present[x]) { x++; } return x; }}Complexity
Time
O(N). Calculating the prefix sum is O(N). Populating the boolean array is O(N). The final `while` loop runs at most a constant number of times (at most 51 times), which is an O(1) operation. The total time complexity is O(N + N + 1) = O(N).
Space
O(1). The boolean array has a fixed size (51) determined by the problem constraints on the values of `nums[i]`, not by the length of the input array `N`.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1), as the extra space used is constant.
Extremely fast in practice due to direct array indexing, avoiding hashing overhead.
Cons
This approach's efficiency relies on the constraint that the values in
numsare within a small, fixed range. It is not a general-purpose solution for arrays with large or unbounded integer values.
Solutions
Solution
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 ; } } } }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 ]; } bitset < 51 > vis ; for ( int x : nums ) { vis [ x ] = 1 ; } for ( int x = s ;; ++ x ) { if ( x >= 51 || ! vis [ x ]) { return x ; } } } };class Solution : def missingInteger ( self , nums : List [ int ]) -> int : s , j = nums [ 0 ], 1 while j < len ( nums ) and nums [ j ] == nums [ j - 1 ] + 1 : s += nums [ j ] j += 1 vis = set ( nums ) for x in count ( s ): if x not in vis : return xVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.