LeetCode 163 Missing Ranges Solution & Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Array Traversal - Iterating through a sorted array while comparing consecutive elements to detect gaps
Interval Representation - Understanding how to construct and return ranges as pairs of start and end values
Edge Case Handling - Managing boundary conditions such as empty arrays, gaps before the first element, and gaps after the last element

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

If the array is empty, the entire range [lower, upper] is missing. Return it as a single range.
Check if there is a gap between lower and nums[0]. If lower < nums[0], add [lower, nums[0] - 1] to the result.
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.
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.
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

class Solution {
    public List<List<Integer>> findMissingRanges(
        int[] nums,
        int lower,
        int upper
    ) {
        int n = nums.length;
        List<List<Integer>> missingRanges = new ArrayList<>();

        if (n == 0) {
            missingRanges.add(Arrays.asList(lower, upper));
            return missingRanges;
        }
        // Check for any missing numbers between the lower bound and nums[0].
        if (lower < nums[0]) {
            missingRanges.add(Arrays.asList(lower, nums[0] - 1));
        }

        // Check for any missing numbers between successive elements of nums.
        for (int i = 0; i < n - 1; i++) {
            if (nums[i + 1] - nums[i] <= 1) {
                continue;
            }
            missingRanges.add(Arrays.asList(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]) {
            missingRanges.add(Arrays.asList(nums[n - 1] + 1, upper));
        }

        return missingRanges;
    }
}

class Solution {
public:
    vector<vector<int>> findMissingRanges(vector<int>& nums, int lower,
                                          int upper) {
        int n = nums.size();
        vector<vector<int>> missingRanges;
        if (n == 0) {
            missingRanges.push_back(vector<int>{lower, upper});
            return missingRanges;
        }

        // Check for any missing numbers between the lower bound and nums[0].
        if (lower < nums[0]) {
            missingRanges.push_back(vector<int>{lower, nums[0] - 1});
        }

        // Check for any missing numbers between successive elements of nums.
        for (int i = 0; i < n - 1; i++) {
            if (nums[i + 1] - nums[i] <= 1) {
                continue;
            }
            missingRanges.push_back(vector<int>{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]) {
            missingRanges.push_back(vector<int>{nums[n - 1] + 1, upper});
        }

        return missingRanges;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} lower
     * @param {number} upper
     * @return {number[][]}
     */
    findMissingRanges(nums, lower, upper) {
        let n = nums.length;
        let missingRanges = [];
        if (n === 0) {
            missingRanges.push([lower, upper]);
            return missingRanges;
        }

        // Check for any missing numbers between the lower bound and nums[0].
        if (lower < nums[0]) {
            missingRanges.push([lower, nums[0] - 1]);
        }

        // Check for any missing numbers between successive elements of nums.
        for (let i = 0; i < n - 1; i++) {
            if (nums[i + 1] - nums[i] <= 1) {
                continue;
            }
            missingRanges.push([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]) {
            missingRanges.push([nums[n - 1] + 1, upper]);
        }

        return missingRanges;
    }
}

public class Solution {
    public IList<IList<int>> FindMissingRanges(int[] nums, int lower, int upper) {
        int n = nums.Length;
        IList<IList<int>> missingRanges = new List<IList<int>>();

        if (n == 0) {
            missingRanges.Add(new List<int> { lower, upper });
            return missingRanges;
        }

        // Check for any missing numbers between the lower bound and nums[0].
        if (lower < nums[0]) {
            missingRanges.Add(new List<int> { lower, nums[0] - 1 });
        }

        // Check for any missing numbers between successive elements of nums.
        for (int i = 0; i < n - 1; i++) {
            if (nums[i + 1] - nums[i] <= 1) {
                continue;
            }
            missingRanges.Add(new List<int> { 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]) {
            missingRanges.Add(new List<int> { nums[n - 1] + 1, upper });
        }

        return missingRanges;
    }
}

func findMissingRanges(nums []int, lower int, upper int) [][]int {
    n := len(nums)
    missingRanges := [][]int{}

    if n == 0 {
        missingRanges = append(missingRanges, []int{lower, upper})
        return missingRanges
    }

    // Check for any missing numbers between the lower bound and nums[0].
    if lower < nums[0] {
        missingRanges = append(missingRanges, []int{lower, nums[0] - 1})
    }

    // Check for any missing numbers between successive elements of nums.
    for i := 0; i < n-1; i++ {
        if nums[i+1]-nums[i] <= 1 {
            continue
        }
        missingRanges = append(missingRanges, []int{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] {
        missingRanges = append(missingRanges, []int{nums[n-1] + 1, upper})
    }

    return missingRanges
}

class Solution {
    fun findMissingRanges(nums: IntArray, lower: Int, upper: Int): List<List<Int>> {
        val n = nums.size
        val missingRanges = mutableListOf<List<Int>>()

        if (n == 0) {
            missingRanges.add(listOf(lower, upper))
            return missingRanges
        }

        // Check for any missing numbers between the lower bound and nums[0].
        if (lower < nums[0]) {
            missingRanges.add(listOf(lower, nums[0] - 1))
        }

        // Check for any missing numbers between successive elements of nums.
        for (i in 0 until n - 1) {
            if (nums[i + 1] - nums[i] <= 1) {
                continue
            }
            missingRanges.add(listOf(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]) {
            missingRanges.add(listOf(nums[n - 1] + 1, upper))
        }

        return missingRanges
    }
}

class Solution {
    func findMissingRanges(_ nums: [Int], _ lower: Int, _ upper: Int) -> [[Int]] {
        let n = nums.count
        var missingRanges = [[Int]]()

        if n == 0 {
            missingRanges.append([lower, upper])
            return missingRanges
        }

        // Check for any missing numbers between the lower bound and nums[0].
        if lower < nums[0] {
            missingRanges.append([lower, nums[0] - 1])
        }

        // Check for any missing numbers between successive elements of nums.
        for i in 0..<(n - 1) {
            if nums[i + 1] - nums[i] <= 1 {
                continue
            }
            missingRanges.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] {
            missingRanges.append([nums[n - 1] + 1, upper])
        }

        return missingRanges
    }
}

impl Solution {
    pub fn find_missing_ranges(nums: Vec<i32>, lower: i32, upper: i32) -> Vec<Vec<i32>> {
        let n = nums.len();
        let mut missing_ranges: Vec<Vec<i32>> = Vec::new();

        if n == 0 {
            missing_ranges.push(vec![lower, upper]);
            return missing_ranges;
        }

        // Check for any missing numbers between the lower bound and nums[0].
        if lower < nums[0] {
            missing_ranges.push(vec![lower, nums[0] - 1]);
        }

        // Check for any missing numbers between successive elements of nums.
        for i in 0..n - 1 {
            if nums[i + 1] - nums[i] <= 1 {
                continue;
            }
            missing_ranges.push(vec![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.push(vec![nums[n - 1] + 1, upper]);
        }

        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.