Missing Ranges
Given a sorted list of distinct numbers inside a range, list the gaps as [start, end] pairs. A careful one-pass scan where the real test is handling the boundaries without off-by-one errors. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an inclusive range [lower, upper] and a sorted array nums of distinct integers, all of which lie inside that range.
A number x is missing if lower ≤ x ≤ upper and x does not appear in nums. Return the shortest sorted list of ranges that covers every missing number and nothing else. Each range is a pair [start, end] with start ≤ end; a single missing number x is written as [x, x].
If nothing is missing, return an empty list.
Example 1
- Input
- nums = [2, 3, 7, 10], lower = 0, upper = 12
- Output
- [[0, 1], [4, 6], [8, 9], [11, 12]]
Each pair is a maximal run of numbers that are not in nums.
Example 2
- Input
- nums = [], lower = 5, upper = 8
- Output
- [[5, 8]]
With no numbers present, the whole range is missing.
Example 3
- Input
- nums = [4, 5, 6], lower = 4, upper = 6
- Output
- []
Every number in the range is present.
Example 4
- Input
- nums = [-3, -1], lower = -3, upper = 0
- Output
- [[-2, -2], [0, 0]]
Constraints
- -10⁹ ≤ lower ≤ upper ≤ 10⁹
- 0 ≤ nums.length ≤ 100
- lower ≤ nums[i] ≤ upper
- nums is sorted in increasing order and all values are distinct.
Practice
Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Missing Ranges in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Missing Ranges
Pattern: Linear scan with sentinels
Because nums is sorted, the missing numbers are exactly the gaps between consecutive present values. If one present value is a and the next is b, then everything from a + 1 to b - 1 is missing, and that's a gap only when b - a > 1.
The gaps at the edges (before the first number and after the last) are the awkward part. A clean trick is to pretend there are two extra present values: lower - 1 before the array and upper + 1 after it. Then every gap, including the edges and the empty-array case, is just "a gap between neighbors", and one loop handles them all.
The range itself can be two billion wide, so never walk through it number by number; only look at the elements of nums.
Approach 1: Walk every number in the range
Put nums in a set, loop x from lower to upper, and group consecutive missing values into runs. Correct, but its cost depends on the width of the range, which can be 2 × 10⁹, not on the size of nums.
Time O(upper - lower) · Space O(n)
Approach 2: Scan neighbors with special edge cases
Handle the gap from lower to nums[0], then each gap between neighbors, then the gap from the last element to upper, with a separate branch for an empty array. Same complexity as the final version but with more places to get an off-by-one wrong.
Time O(n) · Space O(1) besides the output
Approach 3: Single pass with sentinel bounds
- Set
prev = lower - 1. - For each
curinnumsfollowed byupper + 1: ifcur - prev ≥ 2, append[prev + 1, cur - 1]. Then setprev = cur. - Return the list.
The two sentinels mean the first and last gaps need no special code.
Time O(n) · Space O(1) besides the output
| Approach | Time | Space |
|---|---|---|
| Walk every number in the range | O(upper - lower) | O(n) |
| Scan neighbors with special edge cases | O(n) | O(1) besides the output |
| Single pass with sentinel bounds | O(n) | O(1) besides the output |
Solution code
Try the practice editor first. Both solutions pass every test above.
Missing Ranges solution in Python
def find_missing_ranges(nums: list[int], lower: int, upper: int) -> list[list[int]]:
ranges: list[list[int]] = []
prev = lower - 1
for cur in nums + [upper + 1]:
if cur - prev >= 2:
ranges.append([prev + 1, cur - 1])
prev = cur
return rangesMissing Ranges solution in JavaScript
function findMissingRanges(nums, lower, upper) {
const ranges = [];
let prev = lower - 1;
for (const cur of [...nums, upper + 1]) {
if (cur - prev >= 2) ranges.push([prev + 1, cur - 1]);
prev = cur;
}
return ranges;
}Common mistakes
- Iterating from lower to upper one number at a time, which times out when the range is huge.
- Off-by-one errors at the edges, such as reporting [lower, nums[0]] instead of [lower, nums[0] - 1].
- Forgetting the empty-array case, where the whole range [lower, upper] is missing.
- In fixed-width languages, computing lower - 1 or upper + 1 near the integer limits. Use 64-bit arithmetic for the sentinels.
What interviewers look for
This problem has almost no algorithm, so interviewers judge it on precision. State the gap rule clearly ("between neighbors a and b, the missing run is a + 1 through b - 1, and it exists only if b - a ≥ 2"), then show how sentinels remove the edge cases.
Before you finish, run through the edge inputs out loud: an empty array, an array that fills the range, a missing value right at lower, and one right at upper.
Follow-up questions
What if nums could contain duplicates or be unsorted?
Sort it first (O(n log n)), and treat a neighbor with cur == prev as no gap. The gap test cur - prev ≥ 2 already ignores duplicates, so only the sort is new.
What if numbers arrive as a stream and you need the missing ranges at any time?
Maintain the present values as a set of disjoint intervals in a sorted structure (Data Stream as Disjoint Intervals). Each insert merges with at most two neighbors in O(log n), and the missing ranges are the gaps between stored intervals plus the edges.
How would you return the output as strings like "4->6" or "8"?
Generate the same [start, end] pairs, then format each one as a single number when start equals end and as "start->end" otherwise. Keeping the gap logic separate from the formatting keeps both simple.
Companies that ask Missing Ranges
Missing Ranges is tagged by 116 companies in our interview dataset. The score shows how often it comes up at each company.
- Calix100%
- Ramp100%
- Wisetech Global97%
- Cabaletta Bio97%
- Weedmaps87%
- Whoop87%
- Abbott86%
- Chargebee85%
- Bumble84%
- Bae Systems83%
- Realtorcom83%
- Kajabi76%
- Zipline75%
- Dandy75%
- Clever74%
- Clevertap74%
- Amperity73%
- Goodrx72%
- 8451˚72%
- Motorola Solutions72%
- Globallogic71%
- Sortly70%
- Grid Dynamics70%
- Tyler Technologies70%
and 92 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required