# The Missing Number

> Something is missing from the sequence.

Canonical URL: <https://datadriven.io/problems/the_missing_number>

Domain: Python · Difficulty: easy · Seniority: L3

## 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.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the ability to **iterate over gaps in a sorted sequence** efficiently. It checks whether candidates can count missing values without materializing the full sequence, using the relationship between expected and actual positions.

---

### Break down the requirements

#### Step 1: Walk through positive integers starting from 1

Track which positive integer you are currently checking and how many missing ones you have found.

#### Step 2: Use the sorted list to skip present values

If the current positive integer matches the next list element, it is not missing. Advance both pointers.

#### Step 3: Count missing values until you reach n

When the current integer is not in the list, increment the missing count. When the count reaches n, return that integer.

---

### The solution

**Linear scan counting gaps**

```python
def nth_missing(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
```

> **Time and Space Complexity**
>
> **Time:** O(n + m) where m is the length of the input list and n is the target missing number. In the worst case, you scan through the list and count up to n gaps.
> 
> **Space:** O(1). Only three integer variables.

> **Interviewers Watch For**
>
> Can you articulate why this works? The sorted, unique property of the input means each list element eliminates exactly one candidate. Every candidate not in the list is a missing number.

> **Common Pitfall**
>
> Building a set and checking membership in a loop from 1 upward. This works but uses O(m) extra space unnecessarily since the list is already sorted.

---

## Common follow-up questions

- Can you solve this in O(log m) using binary search? _(Tests binary search on the number of missing values before each index.)_
- What if the list were not sorted? _(Tests whether sorting first or using a set changes the approach.)_
- What if n could be very large (e.g., 10^9)? _(Tests the binary search approach to avoid linear scanning.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_missing_number)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.