LeetCode 163: Missing Ranges

Problem Restatement

We are given an inclusive range:

[lower, upper]

We are also given a sorted array nums.

The array contains unique integers, and every number in nums lies inside [lower, upper].

A number is missing if it is inside [lower, upper] but does not appear in nums.

We need to return the shortest sorted list of ranges that exactly covers all missing numbers. Each range is represented as:

[start, end]

For example, if only 2 is missing, we return:

[2, 2]

If all numbers from 4 to 49 are missing, we return:

[4, 49]

LeetCode states that nums is sorted, unique, and all values are inside the inclusive range [lower, upper]. The constraints are 0 <= nums.length <= 100 and -10^9 <= lower <= upper <= 10^9.

Input and Output

Example function shape:

def findMissingRanges(nums: list[int], lower: int, upper: int) -> list[list[int]]:
    ...

Examples

Example 1:

nums = [0, 1, 3, 50, 75]
lower = 0
upper = 99

Numbers covered by nums are:

0, 1, 3, 50, 75

The missing parts are:

2
4 through 49
51 through 74
76 through 99

So the answer is:

[[2, 2], [4, 49], [51, 74], [76, 99]]

Example 2:

nums = [-1]
lower = -1
upper = -1

The only number in the range is -1, and it appears in nums.

So there are no missing ranges:

[]

Example 3:

nums = []
lower = 1
upper = 5

No numbers are present.

So the whole range is missing:

[[1, 5]]

First Thought: Check Every Number

A direct solution is to loop through every integer from lower to upper.

For each number, check whether it appears in nums.

This is not a good idea because the range can be very large.

For example:

lower = -10**9
upper = 10**9

That range contains billions of values.

The array length is small, but the numeric interval can be huge.

So we should not iterate over every number in the range.

Key Insight

Since nums is already sorted, missing numbers appear only in gaps.

There are three kinds of gaps:

For example:

nums = [0, 1, 3, 50, 75]

Between 3 and 50, the missing range is:

[4, 49]

because everything after 3 and before 50 is absent.

Algorithm

Create an empty answer list:

answer = []

If nums is empty, return:

[[lower, upper]]

Otherwise:

1. Check the gap before nums[0].
2. Check every gap between consecutive numbers.
3. Check the gap after nums[-1].
4. Return the collected ranges.

A gap exists between a and b when:

b - a > 1

The missing range is:

[a + 1, b - 1]

Walkthrough

Use:

nums = [0, 1, 3, 50, 75]
lower = 0
upper = 99

Check before the first number:

nums[0] = 0
lower = 0

There is no gap before 0.

Now check adjacent pairs.

Pair 0, 1:

1 - 0 = 1

No missing number.

Pair 1, 3:

3 - 1 = 2

There is a gap:

[2, 2]

Pair 3, 50:

50 - 3 = 47

There is a gap:

[4, 49]

Pair 50, 75:

75 - 50 = 25

There is a gap:

[51, 74]

Check after the last number:

nums[-1] = 75
upper = 99

There is a final gap:

[76, 99]

Final answer:

[[2, 2], [4, 49], [51, 74], [76, 99]]

Correctness

Because nums is sorted, any missing number must lie in one of three places: before the first element, between two adjacent elements, or after the last element.

The algorithm checks the range before the first element. If nums[0] > lower, then every integer from lower through nums[0] - 1 is missing, and the algorithm adds exactly that range.

For each adjacent pair a, b, there are no elements of nums between them. If b - a > 1, then every integer from a + 1 through b - 1 is missing, and the algorithm adds exactly that range. If b - a == 1, no integer can fit between them, so no range is added.

The algorithm also checks the range after the last element. If nums[-1] < upper, then every integer from nums[-1] + 1 through upper is missing, and the algorithm adds exactly that range.

These ranges are produced in sorted order and do not overlap. Together, they cover every missing number and no present number. Therefore, the output is exactly the required shortest sorted list of missing ranges.

Complexity

Let n be the length of nums.

Implementation

class Solution:
    def findMissingRanges(
        self,
        nums: list[int],
        lower: int,
        upper: int,
    ) -> list[list[int]]:
        if not nums:
            return [[lower, upper]]

        answer = []

        if nums[0] > lower:
            answer.append([lower, nums[0] - 1])

        for i in range(1, len(nums)):
            prev = nums[i - 1]
            curr = nums[i]

            if curr - prev > 1:
                answer.append([prev + 1, curr - 1])

        if nums[-1] < upper:
            answer.append([nums[-1] + 1, upper])

        return answer

Code Explanation

The empty-array case is special:

if not nums:
    return [[lower, upper]]

If no values are present, the entire inclusive range is missing.

Then we check whether anything is missing before the first value:

if nums[0] > lower:
    answer.append([lower, nums[0] - 1])

Next, scan adjacent pairs:

for i in range(1, len(nums)):

For each pair:

prev = nums[i - 1]
curr = nums[i]

A missing range exists only when there is space between them:

if curr - prev > 1:
    answer.append([prev + 1, curr - 1])

Finally, check after the last value:

if nums[-1] < upper:
    answer.append([nums[-1] + 1, upper])

Return the collected ranges:

return answer

Sentinel Implementation

We can also simplify the logic by adding virtual boundaries.

Use:

prev = lower - 1

Then scan every number plus a virtual final value:

upper + 1

For each current value curr, the missing range between prev and curr is:

[prev + 1, curr - 1]

when:

curr - prev > 1

Code:

class Solution:
    def findMissingRanges(
        self,
        nums: list[int],
        lower: int,
        upper: int,
    ) -> list[list[int]]:
        answer = []
        prev = lower - 1

        for curr in nums + [upper + 1]:
            if curr - prev > 1:
                answer.append([prev + 1, curr - 1])

            prev = curr

        return answer

This version is shorter.

In languages with fixed-width integers, be careful with lower - 1 and upper + 1 because of overflow. Python integers are arbitrary precision, so this is safe in Python.

Testing

def run_tests():
    sol = Solution()

    assert sol.findMissingRanges([0, 1, 3, 50, 75], 0, 99) == [
        [2, 2],
        [4, 49],
        [51, 74],
        [76, 99],
    ]

    assert sol.findMissingRanges([-1], -1, -1) == []
    assert sol.findMissingRanges([], 1, 5) == [[1, 5]]
    assert sol.findMissingRanges([1, 2, 3], 1, 3) == []
    assert sol.findMissingRanges([2], 1, 3) == [[1, 1], [3, 3]]
    assert sol.findMissingRanges([1, 3], 1, 3) == [[2, 2]]
    assert sol.findMissingRanges([-3, -1, 2], -3, 3) == [[-2, -2], [0, 1], [3, 3]]

    print("all tests passed")

run_tests()