Missing Ranges

Easy · Arrays & Hashing · Explanation and code example

Linear Scan

How it works

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.

Steps

  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.

Complexity

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

Where n is the number of elements in nums.

Things to watch for

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.

Python code example

from typing import List

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

C++ code example

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;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations