The Spaces Between

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
mid
Asked in
Lyft

Problem

We assign every trip a sequential id, but voided and dropped records leave gaps, so the recorded ids arrive sorted and unique with holes between them. Given those recorded ids and a position k, find the k-th id missing from the sequence, counting the gaps starting after the first recorded id. When k runs past every gap inside the recorded range, keep counting beyond the last recorded id.

Every voided trip leaves a hole in the sequence. Find the one that matters.

Example 1

Input:

ids = [2,3,4,7,11], k = 4

Output:

9

Example 2

Input:

ids = [4,7,9,10], k = 5

Output:

12

Worked solution and explanation

Why this problem exists in real interviews

This is a gap-counting problem wearing an auditing costume. Between any two consecutive recorded ids, prev and current, exactly current - prev - 1 integers went missing, and that is a number you read off with a single subtraction. The real trap is reaching for the integers themselves: stepping a cursor up from ids[0] and counting absent values one at a time until you have seen k. That version is correct, and on a sparse id space it is fatal. It is O(answer), so when k is near a billion it walks a billion steps and times out, and the set(range(ids[0], ids[-1])) variant dies even faster at O(max - min) memory. The fix is to never touch the integer range at all. Accumulate the gap counts across the n recorded ids by subtraction, and the moment the running total would pass k, the answer sits inside the current gap. That is O(n) time and O(1) space, and it is the whole skill. Binary search over the (monotonic) running gap count shaves it to O(log n), but it is a refinement on top of the same arithmetic, not what rescues you from the timeout.

Break down the requirements

Step 1: Count each gap with one subtraction

Between consecutive recorded ids prev and current, the absent integers are prev+1 through current-1, so there are current - prev - 1 of them. No loop over those integers is needed to count them, which is the entire point: you learn how many ids vanished in a gap without ever materializing the gap, so a span billions wide costs the same as a span of two.

Step 2: Accumulate across the array until k lands inside a gap

Walk the recorded ids in order, carrying the still-needed count k. For each gap, if k is no larger than that gap's size, the k-th missing id is the k-th integer after prev, namely prev + k, and you are done. Otherwise subtract this gap's size from k and move on. This touches each id once, so it is O(n), and it never enumerates the range between them.

Step 3: Let k run past the last recorded id

If the running k survives every internal gap, the k-th missing id lies beyond ids[-1]. After the loop, prev is the last recorded id and k is whatever is left, so the answer is prev + k. This is also what keeps a giant k cheap: the contiguous case [1, 2, 3] has no internal gaps at all, every requested miss is past the end, and you return in O(n) with a single addition rather than walking a billion values.

The solution

Count gaps by subtraction in a single pass
def kth_missing(ids, k):
    prev = ids[0]
    for i in range(1, len(ids)):
        current = ids[i]
        gap = current - prev - 1   # integers missing between prev and current
        if k <= gap:
            return prev + k        # k-th miss sits inside this gap
        k -= gap                   # consumed this gap, keep looking
        prev = current
    return prev + k                 # k ran past the last id; count beyond it
Linear pass over the array (canonical, O(n))
Walk the recorded ids once, subtract current - prev - 1 to size each gap, and stop when the remaining k falls inside one. O(n) time, O(1) space, easy to defend, and it never enumerates the integer range. This is the answer to ship.
Binary search on the running gap count (O(log n))
Because the cumulative gap count ids[i] - ids[0] - i only climbs, you can bisect for the first index whose count reaches k and back the answer out of the gap just before it. Touches log n elements instead of n. A genuine speedup, but it rests on exactly the same gap arithmetic, so reach for it only after the O(n) version is correct.

Common follow-up questions