💬 Discord
Sign In
NeetCode #829LC-163EasyIntervalsNC Algo100
← Back to All Problems

#829 · #163 · Missing Ranges(缺失的区间)

📌 Problem Statement & Constraints

You are given a sorted integer array nums with distinct values and inclusive bounds lower and upper. Return the list of missing ranges in [lower, upper] as [start, end] pairs. Constraints: -10^9 <= lower <= upper <= 10^9, -10^9 <= nums[i] <= 10^9, nums is sorted and distinct.

💡 Core Algorithmic Approaches

  1. Think of a virtual cursor prev that starts just before lower (at lower - 1).
  2. Walk through nums plus a sentinel upper + 1; for each value v, the gap (prev, v) is missing if v - prev > 1.
  3. Emit [prev + 1, v - 1] for each non-empty gap.
  4. The sentinel handles the tail so no separate case is needed.

💻 Benchmark Python3 Implementation

class Solution:
    def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[List[int]]:
        res = []
        prev = lower - 1                        # cursor just before the range
        for v in nums + [upper + 1]:            # sentinel closes the tail
            if v - prev > 1:
                res.append([prev + 1, v - 1])
            prev = v
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass with O(1) work per element.
💾 Space Complexity
O(n) for the output list.

⚠️ Interview Pitfalls & Follow-ups

  • Using v - prev > 0: a single missing value forms a range of length one, so the gap must be strictly greater than 1.
  • Forgetting the tail: after the last array element there may be a gap up to upper, handled by the upper + 1 sentinel.
  • Emitting empty ranges: when v == prev + 1 there is no gap, so the guard is essential.
  • Underflow on lower - 1: with the stated bounds (about 10^9) this is safe in Python, but in fixed-width languages the sentinel must be chosen carefully.