The Missing Number

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

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
Lyft

Problem

Given a sorted list of distinct positive integers and integer n (1-based), return the n-th positive integer (in 1, 2, 3, ...) that is NOT in the list.

Something is missing from the sequence.

Example 1

Input:

nums = [2,3,5], n = 1

Output:

1

Example 2

Input:

nums = [2,3,5], n = 2

Output:

4

Worked solution and explanation

Counting past the edge of the list

This is unbounded counting against a sparse exclusion list, dressed up as ID assignment. The real skill: walk the positive integers from 1 and tally the ones nums does not claim, then keep walking after nums runs out. Almost everyone reaches for sorted(set(range(1, max(nums)+1)) - set(nums))[n-1], and it looks right on the examples. The trap is the ceiling: max(nums) bounds the search to the list, so the moment the n-th free number lives past the largest taken value (nums=[1, 2, 3, 4], n=10 -> 14) the set difference is empty and you get an IndexError or a too-small answer. An empty list breaks it the same way.

Break down the requirements

Step 1: Walk the positive integers starting from 1

Track which positive integer you are currently checking and how many free ones you have found. current is the candidate, missing_count is the tally.

Step 2: Use the sorted list to skip taken values

Because nums is sorted, a single cursor idx is enough: when nums[idx] equals current, this candidate is taken, so advance idx and move on. No set, no membership scan.

Step 3: Count free values until you reach n

When current is not the next taken value, it is free: bump missing_count, and when it hits n return current. Crucially the idx < len(nums) guard lets the loop keep counting after nums is exhausted, which is exactly what carries you past max(nums).

The solution

Linear scan counting gaps
def the_missing_number(nums, n):
    missing_count = 0
    current = 0
    idx = 0
    while True:
        current += 1
        if idx < len(nums) and nums[idx] == current:
            idx += 1
        else:
            missing_count += 1
            if missing_count == n:
                return current

Common follow-up questions