# Absent Without Leave

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

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

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]`.

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

```python
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
```

> **Time and space**
>
> **Time:** O(n) in the length of `nums`, one pass.
> 
> **Space:** O(g) for the g gaps returned, ignoring output.

> **Interviewers watch for**
>
> Whether you handle the trailing gap after the loop. The empty-list case ([], 1, 5) returns nothing at all unless that final `expected <= upper` check fires.

> **Common pitfall**
>
> Off-by-one on the gap boundary. The gap ends at `num - 1`, never `num`, because `num` is present. Write `num` and every reported range overlaps a real ID.

---

## Common follow-up questions

- What if a single missing value should be reported as just x instead of [x, x]? _(Tests collapsing [x, x] into a scalar at output time.)_
- What changes if the input is no longer guaranteed sorted? _(Tests sorting first, which adds an O(n log n) prepass.)_
- How would you produce the same gap report directly in SQL? _(Tests comparing each row against the previous one to find breaks in a sequence.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/absent_without_leave)
- [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). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.