Learner Level
Implement the findSmallestMissingPositiveSorted method that finds the smallest positive integer missing from a sorted array.
The input contains a sorted integer array nums and its length size. Your task is to find the smallest positive integer that is missing from the array.
For example, in [1,2,3,5], the smallest missing positive number is 4. In [2,3,4], the answer is 1 because 1 is not present.
Example 1
Input
nums (int[]) =
[1,2,3,5]size (int) =
4Returns (int)
4Example 2
Input
nums (int[]) =
[2,3,4]size (int) =
3Returns (int)
1Example 3
Input
nums (int[]) =
[1,2,3]size (int) =
3Returns (int)
4Since the array is sorted, keep track of the next positive number you expect to see.
Start with expected = 1. Scan the array from left to right. If the current number is equal to expected, move to the next expected number. If the current number becomes greater than expected, then expected is missing and can be returned.
After scanning all values, the current expected value is the smallest missing positive number.
Pseudocode:
function findSmallestMissingPositiveSorted(nums, size):
expected = 1
for i from 0 to size - 1:
if nums[i] == expected:
expected++
else if nums[i] > expected:
break
return expectedReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run