Domain 1EasyCORE

Missing Ranges

The problem requires identifying missing ranges in a given inclusive range `[lower, upper]` that are not present in a sorted unique integer array `nums`. The output should be the smallest sorted list of ranges covering all missing numbers. Each range should be formatted as `"a->b"` if `a != b`, or simply `"a"` if `a == b`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

163. Missing Ranges

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 27.4%


Problem Breakdown

The problem requires identifying missing ranges in a given inclusive range [lower, upper] that are not present in a sorted unique integer array nums. The output should be the smallest sorted list of ranges covering all missing numbers. Each range should be formatted as "a->b" if a != b, or simply "a" if a == b.

Inputs:

  • A sorted unique integer array nums.
  • An inclusive lower bound lower.
  • An inclusive upper bound upper.

Outputs:

  • A list of strings representing the missing ranges.

Implicit Constraints and Edge Cases:

  • The array nums can be empty.
  • The range [lower, upper] can include negative numbers.
  • The range can span a large number of integers, up to (10^9).
  • The array nums is sorted and contains unique elements.

Intuition

A brute-force approach would involve iterating through every integer in the range [lower, upper] and checking if it exists in nums. This approach is inefficient due to its linear time complexity relative to the size of the range. Instead, we can leverage the fact that nums is sorted to identify gaps between consecutive elements efficiently.

The key insight is to iterate through nums and check for gaps between each pair of consecutive numbers (including the gap before the first element and after the last element). If a gap exists, we format it as a range and add it to the result list.

Approach

  1. Initialize an empty list result to store the missing ranges.
  2. Iterate through nums with two pointers: prev initialized to lower - 1 and curr initialized to each element in nums.
  3. For each pair (prev, curr), check if there is a gap:
    • If prev + 1 < curr, add the range "prev+1->curr-1" to result.
    • If prev + 1 == curr, add the single number "prev+1" to result.
  4. After the loop, handle the gap after the last element in nums:
    • If prev + 1 < upper, add the range "prev+1->upper" to result.
    • If prev + 1 == upper, add the single number "prev+1" to result.
  5. Return the result list.

Complexity Analysis

  • Time Complexity: (O(n)), where (n) is the length of nums. We iterate through nums once.
  • Space Complexity: (O(1)) for the additional variables used, excluding the space required for the output list.

Solution

def findMissingRanges(nums, lower, upper):
    result = []
    prev = lower - 1
    
    for curr in nums:
        if prev + 1 < curr:
            result.append(f"{prev+1}->{curr-1}")
        elif prev + 1 == curr:
            result.append(str(prev+1))
        prev = curr
    
    if prev + 1 < upper:
        result.append(f"{prev+1}->{upper}")
    elif prev + 1 == upper:
        result.append(str(prev+1))
    
    return result

Edge Cases Handled

  • Empty nums: The loop does not execute, and the final check handles the entire range [lower, upper].
  • Single element in nums: The loop processes one element, and the final check handles any remaining range.
  • No missing ranges: If all numbers from lower to upper are present in nums, the result remains empty.
  • Negative numbers: The algorithm correctly handles negative numbers by using arithmetic operations.
  • Large range: The algorithm efficiently processes large ranges due to its linear time complexity.