Missing Ranges
Easy · Intervals · Array
Problem
You are given an inclusive range [lower, upper] and a sorted array nums of unique integers, all of which lie inside that range.
A number is *missing* if it is in [lower, upper] but not in nums. Return the shortest sorted list of ranges [a, b] that covers exactly the missing numbers, with no overlap between ranges. A single missing number x is the range [x, x].
Examples
Input: nums = [2,3,7], lower = 0, upper = 9 Output: [[0,1],[4,6],[8,9]]
0..1, 4..6 and 8..9 are absent from nums.
Input: nums = [5], lower = 5, upper = 5 Output: []
Every number in the range is present.
Input: nums = [], lower = 1, upper = 4 Output: [[1,4]]
With nothing present, the whole range is missing.
Constraints
- -10^9 <= lower <= upper <= 10^9
- 0 <= len(nums) <= 100
- lower <= nums[i] <= upper
- All values of nums are unique and sorted in ascending order.
Approaches
- Try each possible start, scan for its end — time O(n²), space O(1) beyond the answer
Follow-up
What if nums were unsorted, had duplicates, or contained values outside [lower, upper]? Sort, skip duplicates and clip to the range, then run the same scan.
Related problems
Start free on Cariara · Coding problems · System design studio
