1. Linear Scan

Intuition

We need to identify all gaps in the range [lower, upper] that are not covered by the sorted array nums. There are three places where gaps can occur: before the first element, between consecutive elements, and after the last element. By checking each of these locations, we can collect all missing ranges in a single pass.

Algorithm

1. If the array is empty, the entire range [lower, upper] is missing. Return it as a single range.
2. Check if there is a gap between lower and nums[0]. If lower < nums[0], add [lower, nums[0] - 1] to the result.
3. Iterate through consecutive pairs in the array. For each pair (nums[i], nums[i + 1]):
   • If the difference is greater than 1, there is a gap. Add [nums[i] + 1, nums[i + 1] - 1] to the result.
4. Check if there is a gap between nums[n - 1] and upper. If upper > nums[n - 1], add [nums[n - 1] + 1, upper] to the result.
5. Return the list of missing ranges.

class Solution:
    def findMissingRanges(
        self, nums: List[int], lower: int, upper: int
    ) -> List[List[int]]:
        n = len(nums)
        missing_ranges = []
        if n == 0:
            missing_ranges.append([lower, upper])
            return missing_ranges

        # Check for any missing numbers between the lower bound and nums[0].
        if lower < nums[0]:
            missing_ranges.append([lower, nums[0] - 1])

        # Check for any missing numbers between successive elements of nums.
        for i in range(n - 1):
            if nums[i + 1] - nums[i] <= 1:
                continue
            missing_ranges.append([nums[i] + 1, nums[i + 1] - 1])

        # Check for any missing numbers between the last element of nums and the upper bound.
        if upper > nums[n - 1]:
            missing_ranges.append([nums[n - 1] + 1, upper])

        return missing_ranges

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ constant space

Where $n$ is the number of elements in nums.

Common Pitfalls

Forgetting the Empty Array Case

When nums is empty, the entire range [lower, upper] is missing. Failing to handle this edge case before iterating through the array leads to index out-of-bounds errors or incorrect results. Always check for an empty array first and return [lower, upper] as the single missing range.

Off-by-One Errors in Range Boundaries

A common mistake is using incorrect boundary calculations when constructing missing ranges. For gaps before the first element, the range should be [lower, nums[0] - 1], not [lower, nums[0]]. Similarly, for gaps between consecutive elements, the range is [nums[i] + 1, nums[i + 1] - 1]. Using <= instead of < in comparisons or forgetting to add/subtract 1 from boundaries results in including existing elements or missing valid gaps.