Missing Ranges

Difficulty: Easy | Acceptance: N/A | Paid: No Topics: Array

You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.

A number x is considered missing if x is in the range [lower, upper] and x is not in nums.

Return the smallest sorted list of ranges that exactly cover all the missing numbers. That is, no element of nums is included in any of the ranges, and each missing number is covered by one of the ranges.

Each range [a,b] should be output as: “a->b” if a != b “a” if a == b

• Examples
• Constraints
• Approach 1: Iterative Scan with Sentinels
• Approach 2: Segment Boundary Check

Examples

Example 1:

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: ["2","4->49","51->74","76->99"]
Explanation: The ranges are:
[2,2] --> "2"
[4,49] --> "4->49"
[51,74] --> "51->74"
[76,99] --> "76->99"

Example 2:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing numbers since [-1,-1] is covered by -1 in nums.

Example 3:

Input: nums = [], lower = 1, upper = 1
Output: ["1"]
Explanation: The only missing number is 1.

Constraints

0 <= nums.length <= 100
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= lower <= upper <= 10⁹
nums is sorted in ascending order and contains unique elements.

Approach 1: Iterative Scan with Sentinels

Intuition We can iterate through the numbers while keeping track of the “previous” number that should have been present. By conceptually adding lower - 1 before the array and upper + 1 after the array, we can handle all gaps uniformly using a single loop.

Steps

• Initialize prev to lower - 1.
• Iterate through the array, treating the current element as curr.
• If curr - prev > 1, it means there is a gap between prev and curr. Add the range [prev + 1, curr - 1] to the result.
• Update prev to curr.
• After the loop, perform one final check between the last element and upper + 1.

class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
        res = []
        prev = lower - 1
        for i in range(len(nums) + 1):
            curr = nums[i] if i < len(nums) else upper + 1
            if curr - prev > 1:
                res.append(self.formatRange(prev + 1, curr - 1))
            prev = curr
        return res

    def formatRange(self, lower, upper):
        if lower == upper:
            return str(lower)
        return str(lower) + "->" + str(upper)

Complexity

• Time: O(N) where N is the length of the array.
• Space: O(1) auxiliary space (excluding the output list).
• Notes: Using long (in Java/C++) or handling arithmetic carefully prevents overflow when lower is at the minimum integer value.

Approach 2: Segment Boundary Check

Intuition Instead of using sentinel values, we explicitly check the three segments where missing numbers can occur: before the first element, between elements, and after the last element.

Steps

• Check the range from lower to nums[0] - 1. If valid, add to result.
• Iterate through the array from index 1 to the end. Check the range from nums[i-1] + 1 to nums[i] - 1. If valid, add to result.
• Check the range from nums[last] + 1 to upper. If valid, add to result.
• Handle edge cases where the array is empty (range is just lower to upper).

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

        # Check start
        if nums[0] > lower:
            res.append(self.formatRange(lower, nums[0] - 1))

        # Check middle
        for i in range(1, n):
            if nums[i] > nums[i-1] + 1:
                res.append(self.formatRange(nums[i-1] + 1, nums[i] - 1))

        # Check end
        if nums[-1] < upper:
            res.append(self.formatRange(nums[-1] + 1, upper))

        return res

    def formatRange(self, lower, upper):
        if lower == upper:
            return str(lower)
        return str(lower) + "->" + str(upper)

Complexity

• Time: O(N) where N is the length of the array.
• Space: O(1) auxiliary space.
• Notes: This approach requires more conditional checks (start, middle, end) compared to the sentinel approach, but it is equally efficient.