Missing Ranges within Inclusive Bounds
Reported by candidates from ZipRecruiter's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
ZipRecruiter reportedly put this one in front of candidates in February 2021, and it looks easier than it is. Strip the wrapper and it's one linear scan over a sorted array, tracking the gaps between neighbors and the two edges. Nothing fancy. The points get lost on boundary math and a weird output format, where singletons come back as [x] and longer gaps as [start, end]. If you blank on the edges mid-assessment, StealthCoder runs invisibly on your desktop and hands you a working solution. But you can learn this one tonight.
The problem
nums is sorted, contains unique integers, and every value lies inside inclusive [lower, upper]. Return every maximal missing interval in ascending order. Encode a singleton as [x] and a longer interval as [start, end]. Function missingRanges(nums: int[], lower: int, upper: int) → int[][] Examples Example 1 nums = [0,1,3,50,75] lower = 0 upper = 99 return = [[2],[4,49],[51,74],[76,99]] Leading, singleton, middle, and trailing gaps are returned in order. Example 2 nums = [] lower = 3 upper = 4 return = [[3,4]] The inclusive contract returns the full missing range. Constraints 0 <= nums.length <= 100000 -1000000000 <= lower <= upper <= 1000000000
Reported by candidates. Source: FastPrep
Pattern and pitfall
The reduction: pretend there's a sentinel at lower - 1 and another at upper + 1, then compare each consecutive pair. For prev and cur, if cur - prev >= 2, a gap exists from prev + 1 to cur - 1. If the two ends are equal, emit [x]. Otherwise emit [start, end]. Walk the array once, O(n) time, and the output is the only extra space. The pitfalls are all edges. An empty nums must return [[lower, upper]] when the range is non-empty. Values can sit exactly on lower or upper, which produces no gap. Don't special-case the head and tail with separate code, the sentinels handle both. With bounds near a billion, Python is safe, but in a fixed-width language watch overflow on lower - 1 and upper + 1. If the live OA freezes you, StealthCoder is the hedge that gets the boundaries right.
Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.
You can drill Missing Ranges within Inclusive Bounds cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as missing ranges. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass ZipRecruiter's OA.
ZipRecruiter reuses patterns across OAs. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Missing Ranges within Inclusive Bounds FAQ
What's the trick to Missing Ranges?+
Add virtual sentinels at lower - 1 and upper + 1, then check every adjacent pair. If the difference is 2 or more, there's a gap from prev + 1 to cur - 1. This removes the separate leading and trailing cases and keeps the loop to a few lines.
How hard is this really?+
Easy on algorithm, annoying on details. The scan is linear and obvious. What costs people is off-by-one errors, the empty array case, and formatting singletons as [x] instead of [x, x]. Test those three by hand before submitting.
How should I format singleton ranges?+
If start equals end, output a one-element list like [2]. Otherwise output [start, end]. Example 1 shows both forms, [2] and [4,49]. Mixing them up fails otherwise correct solutions, so build the output with one small helper.
What edge cases should I test?+
Test empty nums with lower less than upper, and with lower equal to upper. Test nums that include lower or upper exactly. Test a fully covered range, which returns an empty list. Test a gap of exactly one number. Those cover nearly every wrong answer.
How do I prepare in 48 hours?+
Write this from scratch twice, once with sentinels and once with explicit head and tail handling, and compare. Then do a couple of sorted-array interval problems for the same boundary thinking. Don't memorize code. Memorize the rule that a gap exists when the difference is at least 2.