Find smallest missing number in sorted array

Problem

Given a sorted array of n distinct integers where each integer is in the range from 0 to m-1 and m > n, find the smallest number that is missing from the array.

Note: This is a special case of [Missing Element in Sorted Array](missing-element-in-sorted-array) with k=1.

Examples

Example 1

Input: nums = [0, 1, 2, 6, 9], n = 5, m = 10
Output: 3

Example 2

Input: [4, 5, 10, 11], n = 4, m = 12
Output: 0

Solution

Method 1 – Linear Scan

If arr[0] != 0, return 0. Otherwise, scan the array and return the first index where arr[i] != i. This approach takes O(n) time.

Method 2 – Modified Binary Search (Optimal)

This is the optimal approach for sorted arrays with distinct elements. Compare the value at each index with the index itself:

Code

C++

class Solution {
public:
    int findSmallestMissing(const vector<int>& arr) {
        return helper(arr, 0, arr.size() - 1);
    }
private:
    int helper(const vector<int>& arr, int start, int end) {
        if (start > end) return end + 1;
        if (arr[start] != start) return start;
        int mid = (start + end) / 2;
        if (arr[mid] == mid)
            return helper(arr, mid + 1, end);
        else
            return helper(arr, start, mid);
    }
};

Go

type Solution struct{}

func (s Solution) FindSmallestMissing(arr []int) int {
    var helper func(start, end int) int
    helper = func(start, end int) int {
        if start > end {
            return end + 1
        }
        if arr[start] != start {
            return start
        }
        mid := (start + end) / 2
        if arr[mid] == mid {
            return helper(mid+1, end)
        } else {
            return helper(start, mid)
        }
    }
    return helper(0, len(arr)-1)
}

Java

class Solution {
    public int findSmallestMissing(int[] arr) {
        return helper(arr, 0, arr.length - 1);
    }
    private int helper(int[] arr, int start, int end) {
        if (start > end) return end + 1;
        if (arr[start] != start) return start;
        int mid = (start + end) / 2;
        if (arr[mid] == mid)
            return helper(arr, mid + 1, end);
        else
            return helper(arr, start, mid);
    }
}

Python

from typing import List
class Solution:
    def findSmallestMissing(self, arr: List[int]) -> int:
        def helper(start: int, end: int) -> int:
            if start > end:
                return end + 1
            if arr[start] != start:
                return start
            mid = (start + end) // 2
            if arr[mid] == mid:
                return helper(mid + 1, end)
            else:
                return helper(start, mid)
        return helper(0, len(arr) - 1)

Complexity

• ⏰ Time complexity: O(log n), because each step of the binary search halves the search space, leading to logarithmic time in the size of the array.
• 🧺 Space complexity: O(1), as the algorithm uses only a constant amount of extra space for pointers/indices and recursion stack (if implemented recursively).