Missing Ranges
Understanding the Problem
The task is to find the gaps between consecutive numbers in the array, with one added complication: the range [lower, upper] extends beyond the array itself. A correct solution has to account for gaps before the first element and after the last element, not only the gaps strictly between array elements.
Because the array is sorted and holds unique values, the missing numbers form contiguous blocks that sit between consecutive elements (and between the boundaries lower/upper and the nearest element). A missing block exists wherever two consecutive values differ by more than 1. That observation reduces the whole problem to a single linear scan.
Key Constraints:
0 <= nums.length <= 100→ n is small, so correctness and clean boundary handling matter more than asymptotic speed. A single linear pass already suffices.-10^9 <= lower <= upper <= 10^9→ Values span almost the full signed 32-bit range. The largest difference computed by either approach is at most about2x10^9, which stays below the int32 limit of2.147x10^9, so plainintis safe and no 64-bit type is required.numsis sorted and unique → No sorting or deduplication needed. The ordering alone drives the scan.
Approach 1: Check Each Gap Separately
Intuition
Handle the three kinds of gaps in three separate steps. First, the gap between lower and the first element. Then the gaps between consecutive elements. Finally, the gap between the last element and upper. Each step gets its own block of code, which keeps the boundary logic explicit at the cost of some repetition.
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.
The three blocks above do the same gap check three times. The next approach folds them into one loop by adding virtual boundary elements at each end of the array.
Approach 2: Unified Boundary Scan (Optimal)
Intuition
Treat lower - 1 as a virtual element before the array and upper + 1 as a virtual element after it. With those two anchors in place, every gap check follows the same pattern. The separate code for "before the first element," "between elements," and "after the last element" collapses into one rule applied to consecutive entries of the extended sequence.
The empty-array case falls out of the same rule without special handling. When nums is empty, the loop runs once with prev = lower - 1 and curr = upper + 1. The check curr - prev > 1 becomes (upper + 1) - (lower - 1) > 1, which simplifies to upper >= lower. That always holds given the constraints, so the single range [lower, upper] is added, exactly the expected output for an empty array.
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.