Missing Ranges
Last Updated: March 31, 2026
Understanding the Problem
At first glance, this seems simple: just find the gaps between consecutive numbers in the array, relative to a given range. But there are a few subtleties that make it tricky. The range [lower, upper] extends beyond the array itself, so you need to account for gaps before the first element and after the last element.
The key observation is that the array is already sorted and contains unique values. So the "gaps" are just the spaces between consecutive elements (including the boundaries lower and upper). If you think of it as walking through a series of expected values and checking whether each one exists, the problem becomes a straightforward linear scan.
Key Constraints:
0 <= nums.length <= 100→ With n up to 100, even O(n^2) is trivially fast. The focus here is on correctness and clean logic, not performance optimization.-10^9 <= lower <= upper <= 10^9→ Values span a large integer range. Watch out for integer overflow if you try arithmetic likeupper - lower + 1in languages with fixed-width integers.numsis sorted and unique → No need to sort or deduplicate. We can rely on the ordering for a single linear pass.
Approach 1: Check Each Gap Separately
Intuition
The most straightforward way to think about this: walk through the array and check three types of gaps separately. First, is there a gap between lower and the first element? Then, are there gaps between consecutive elements? Finally, is there a gap between the last element and upper?
This approach handles each case with its own block of code, which is easy to understand but a bit repetitive.
Algorithm
- Handle the edge case where
numsis empty: the entire range[lower, upper]is missing. - Check if there's a gap between
lowerandnums[0]. Iflower < nums[0], add the range[lower, nums[0] - 1]. - For each pair of consecutive elements
nums[i]andnums[i+1], check ifnums[i+1] - nums[i] > 1. If so, add the range[nums[i] + 1, nums[i+1] - 1]. - Check if there's a gap between
nums[n-1]andupper. Ifnums[n-1] < upper, add the range[nums[n-1] + 1, upper].
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the array once, checking each consecutive pair. Each gap check is O(1), so the total is O(n).
- Space Complexity: O(1). Ignoring the output list, we only use a few variables.
This approach works correctly but handles three separate cases with nearly identical logic. What if we could unify all gap checks into a single loop using virtual boundary elements?
Approach 2: Unified Boundary Scan (Optimal)
Intuition
If we treat lower - 1 as a virtual element before the array and upper + 1 as a virtual element after the array, then every gap check follows the exact same pattern. We no longer need separate code for "before the first element," "between elements," and "after the last element." They all become gaps between consecutive entries in an extended sequence.
The trick is that lower - 1 and upper + 1 act as "virtual fence posts" around the array. Every pair of consecutive fence posts (whether real or virtual) is checked identically. If the gap between them is more than 1, there are missing numbers in between. The range [prev + 1, curr - 1] captures exactly those missing numbers.
This works for the empty array too. When nums is empty, the loop runs once with prev = lower - 1 and curr = upper + 1. If upper + 1 - (lower - 1) > 1 (which simplifies to upper >= lower, always true given the constraints), we add the range [lower, upper]. No special case needed.
Algorithm
- Initialize
prev = lower - 1. This represents the element "just before" the range starts. - Iterate through the array. For each element
nums[i], check ifnums[i] - prev > 1. If so, add the range[prev + 1, nums[i] - 1]to the result. - After processing each element, update
prev = nums[i]. - After the loop, do one final check: if
upper + 1 - prev > 1(equivalently,prev < upper), add the range[prev + 1, upper].
Example Walkthrough
Code
- Time Complexity: O(n). Single pass through the array, O(1) work per element. Same asymptotic complexity as Approach 1.
- Space Complexity: O(1). Only a few integer variables beyond the output list.