LeetCode 163 - Missing Ranges

This problem gives us three inputs: - A sorted array nums - A lower bound lower - An upper bound upper The array contains unique integers, and every number in the array lies within the inclusive range [lower, upper].

leetcodeeasyarray

LeetCode Problem 163

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 163 - Missing Ranges

Problem Understanding

This problem gives us three inputs:

  • A sorted array nums
  • A lower bound lower
  • An upper bound upper

The array contains unique integers, and every number in the array lies within the inclusive range [lower, upper].

We must find every number in that range that does not appear in nums. Instead of returning every missing number individually, we must compress consecutive missing numbers into ranges.

For example, if the missing numbers are:

2, 4,5,6,7,8,9

then the output should be:

[[2,2],[4,9]]

The result must satisfy several conditions:

  • Every missing number must appear in exactly one returned range
  • No number from nums may appear in a returned range
  • The ranges must be sorted
  • The representation must be minimal, meaning consecutive missing numbers are merged together

The constraints are relatively small:

  • nums.length <= 100
  • Values range from -10^9 to 10^9

The small input size means even less efficient solutions could technically pass, but the problem is designed to test careful interval handling and edge-case management.

Several edge cases are especially important:

  • nums can be empty
  • There may be no missing numbers
  • Missing ranges may appear before the first element
  • Missing ranges may appear after the last element
  • Missing ranges may exist between adjacent elements
  • Consecutive numbers should not create ranges
  • Single missing numbers must still be represented as [x, x]

Because the values can be as large as 10^9, we should avoid brute-force iteration across the entire numeric range.

Approaches

Brute Force Approach

A straightforward solution is to iterate through every integer from lower to upper and check whether it exists in nums.

To make membership checking efficient, we could place all numbers from nums into a hash set. Then, for every value in the interval:

  1. Check whether it is missing
  2. Group consecutive missing values together
  3. Append completed ranges to the answer

This approach is correct because it explicitly examines every number in the range and identifies all missing values.

However, this becomes impractical when the interval is very large. The difference between upper and lower can be up to 2 * 10^9, so iterating through the entire range would be far too slow.

Optimal Approach

The key observation is that we do not need to examine every integer individually.

Since nums is already sorted and unique, the missing ranges can only exist:

  • Before the first number
  • Between two consecutive numbers
  • After the last number

Instead of checking every value, we only need to examine the gaps between numbers.

Suppose we are currently expecting the next valid number to be current.

When we encounter a number num:

  • If num > current, then the interval [current, num - 1] is missing
  • After processing num, the next expected value becomes num + 1

After processing the entire array, if current <= upper, then the remaining range [current, upper] is missing.

This transforms the problem from scanning an enormous numeric interval into simply scanning the input array once.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(upper - lower + 1) O(n) Iterates through every number in the interval
Optimal O(n) O(1) excluding output Uses gaps between sorted numbers

Algorithm Walkthrough

  1. Initialize an empty result list that will store all missing ranges.
  2. Create a variable called current and set it equal to lower. This variable represents the smallest number that we still need to account for.
  3. Iterate through each number num in nums.
  4. For each num, compare it with current.
  5. If num > current, then every value from current through num - 1 is missing. Add the range [current, num - 1] to the result.
  6. Move current forward to num + 1, because num itself is present in the array and no longer needs consideration.
  7. Continue this process for every element in nums.
  8. After the loop finishes, there may still be a missing range at the end. If current <= upper, append [current, upper].
  9. Return the completed result list.

Why it works

The algorithm maintains the invariant that all numbers smaller than current have already been processed correctly.

Whenever we encounter a number larger than current, the gap between them must consist entirely of missing numbers because the array is sorted and contains unique values.

By processing gaps one at a time, we cover every missing number exactly once without overlap or omission.

Python Solution

from typing import List

class Solution:
    def findMissingRanges(
        self,
        nums: List[int],
        lower: int,
        upper: int
    ) -> List[List[int]]:
        
        missing_ranges = []
        current = lower

        for num in nums:
            if num > current:
                missing_ranges.append([current, num - 1])

            current = num + 1

        if current <= upper:
            missing_ranges.append([current, upper])

        return missing_ranges

The implementation follows the algorithm directly.

The variable missing_ranges stores the final answer.

The variable current tracks the next value that has not yet been accounted for. Initially, this is lower.

During iteration:

  • If num > current, then a missing interval exists
  • That interval is appended immediately
  • Then current advances to num + 1

Advancing to num + 1 works because num itself exists in the array and therefore cannot be part of a missing range.

After processing all numbers, we perform one final check to determine whether a trailing missing interval still exists between current and upper.

The algorithm never iterates through actual numeric ranges, which keeps it efficient even when the interval size is extremely large.

Go Solution

func findMissingRanges(nums []int, lower int, upper int) [][]int {
    result := [][]int{}
    current := lower

    for _, num := range nums {
        if num > current {
            result = append(result, []int{current, num - 1})
        }

        current = num + 1
    }

    if current <= upper {
        result = append(result, []int{current, upper})
    }

    return result
}

The Go implementation mirrors the Python logic closely.

The result is stored as a slice of integer slices, [][]int.

Unlike Python, Go distinguishes between nil slices and empty slices, but both are acceptable for LeetCode output. Initializing with [][]int{} ensures we return an empty slice when no ranges exist.

Integer overflow is not an issue here because the constraints stay safely within Go's standard integer range.

Worked Examples

Example 1

Input:

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

Initial state:

current = 0
result = []
Current num current before Missing range added current after Result
0 0 none 1 []
1 1 none 2 []
3 2 [2,2] 4 [[2,2]]
50 4 [4,49] 51 [[2,2],[4,49]]
75 51 [51,74] 76 [[2,2],[4,49],[51,74]]

After the loop:

current = 76
upper = 99

Since 76 <= 99, append [76,99].

Final result:

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

Example 2

Input:

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

Initial state:

current = -1
result = []
Current num current before Missing range added current after Result
-1 -1 none 0 []

After the loop:

current = 0
upper = -1

Since 0 <= -1 is false, no additional range is added.

Final result:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each array element is processed once
Space O(1) excluding output Only a few variables are used

The algorithm performs a single linear pass through nums.

No auxiliary data structures proportional to input size are required. The only extra memory used is the output list itself, which is not counted toward auxiliary space complexity.

Test Cases

from typing import List

class Solution:
    def findMissingRanges(
        self,
        nums: List[int],
        lower: int,
        upper: int
    ) -> List[List[int]]:
        
        missing_ranges = []
        current = lower

        for num in nums:
            if num > current:
                missing_ranges.append([current, num - 1])

            current = num + 1

        if current <= upper:
            missing_ranges.append([current, upper])

        return missing_ranges

solution = Solution()

# Example case from problem statement
assert solution.findMissingRanges(
    [0,1,3,50,75],
    0,
    99
) == [[2,2],[4,49],[51,74],[76,99]]

# No missing numbers
assert solution.findMissingRanges(
    [-1],
    -1,
    -1
) == []

# Empty nums, entire range missing
assert solution.findMissingRanges(
    [],
    1,
    5
) == [[1,5]]

# Single missing number in middle
assert solution.findMissingRanges(
    [1,3],
    1,
    3
) == [[2,2]]

# Missing range before first element
assert solution.findMissingRanges(
    [5,6],
    1,
    6
) == [[1,4]]

# Missing range after last element
assert solution.findMissingRanges(
    [1,2],
    1,
    5
) == [[3,5]]

# Multiple separated ranges
assert solution.findMissingRanges(
    [2,4,7],
    1,
    10
) == [[1,1],[3,3],[5,6],[8,10]]

# Entire range covered
assert solution.findMissingRanges(
    [1,2,3,4],
    1,
    4
) == []

# Single element range that is missing
assert solution.findMissingRanges(
    [],
    7,
    7
) == [[7,7]]

# Large values
assert solution.findMissingRanges(
    [-1000000000, 1000000000],
    -1000000000,
    1000000000
) == [[-999999999, 999999999]]

Test Case Summary

Test Why
[0,1,3,50,75] Standard example with multiple gaps
[-1] No missing numbers
[] with [1,5] Entire interval missing
[1,3] Single missing value
[5,6] Missing range at beginning
[1,2] Missing range at end
[2,4,7] Multiple disconnected missing ranges
[1,2,3,4] Complete coverage of interval
[] with [7,7] Single-value interval
Extreme values Verifies large integer handling

Edge Cases

Empty Input Array

When nums is empty, the entire interval from lower to upper is missing.

This case can easily break implementations that assume at least one array element exists. The current implementation handles it naturally because the loop never runs, and the final check appends [lower, upper].

No Missing Numbers

If every value in the interval exists in nums, the correct output is an empty list.

A common bug is accidentally generating invalid ranges such as [x, x - 1]. The implementation avoids this by only appending ranges when num > current.

Missing Range at the End

Many implementations correctly process gaps between elements but forget to check for a remaining gap after the final number.

For example:

nums = [1,2]
lower = 1
upper = 5

The missing range [3,5] appears after the loop ends. The final condition:

if current <= upper:

ensures trailing ranges are handled correctly.

Single Missing Number

A missing range may contain exactly one number.

For example:

nums = [1,3]
lower = 1
upper = 3

The missing value is 2, which must be represented as [2,2].

Some implementations incorrectly special-case single values into a different format. This solution treats all ranges uniformly, which keeps the logic simple and correct.