Absent Without Leave

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4

Problem

A monitoring export hands you the sorted, distinct record IDs that actually landed in a log, plus the inclusive lower and upper bounds of the ID range that should have been there. Return the [start, end] ranges covering every ID in [lower, upper] that is absent from nums, each range stretched as wide as it can go and a lone missing ID written as [x, x].

Between the first name and the last, the ones who never showed. Account for them.

Example 1

Input:

nums = [0,1,3,50,75], lower = 0, upper = 99

Output:

[[2,2],[4,49],[51,74],[76,99]]

Example 2

Input:

nums = [], lower = 1, upper = 5

Output:

[[1,5]]

Worked solution and explanation

What this really is

Strip the costume and this is contiguous-gap detection over a sorted sequence: you are reconstructing the holes between the values that are present. Anyone can see that 2 is missing from [0, 1, 3]. What separates candidates is the bookkeeping at the two ends (the gap before the first element and the trailing gap after the last) plus the off-by-one: a gap ends at num minus 1, not num, because num itself is present. Miss the trailing check and every range that runs to upper silently disappears.

How to get there

Step 1: Track the next expected ID

Hold a single cursor, expected, for the next ID you would hope to see. It starts at lower, not at the first element, so a gap that opens before nums[0] gets caught.

Step 2: Emit a gap whenever the cursor falls behind

When the current number jumps past expected, the stretch [expected, num - 1] is the gap. Then advance expected to num + 1, since num is now accounted for. A gap of width one falls out naturally as [x, x].

Step 3: Close out the tail

After the loop, expected may still sit at or below upper. That leftover is the trailing gap [expected, upper]. This is the line candidates forget, and it is the one the empty-list case depends on.

The solution

Linear scan with an expected-value cursor
def find_missing_ranges(nums: list, lower: int, upper: int) -> list:
    gaps = []
    expected = lower
    for num in nums:
        if num > expected:
            gaps.append([expected, num - 1])
        expected = num + 1
    if expected <= upper:
        gaps.append([expected, upper])
    return gaps

Common follow-up questions