Array Linear Search Sorting
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) = 4
Return:
(int) 4
Example 2
Input:
nums (int[]) = [2,3,4]
size (int) = 3
Return:
(int) 1
Example 3
Input:
nums (int[]) = [1,2,3]
size (int) = 3
Return:
(int) 4

Since 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 expected
Run your code to see the result.