Find Missing Elements — 🔴 Advanced (3/3) — LeetCode Daily Python Solution (the trick nobody sees)

Introduction

Missing-number problems show up constantly in interviews because they test something more valuable than "do you know a hash set." They test whether you can spot a hidden structural property in the data and exploit it to shrink your memory footprint. The problem in this video — find every missing element in a contiguous range — has an obvious O(n) time, O(n) space solution that almost everyone reaches for immediately. The interesting version of this problem asks you to keep the O(n) time but drop the extra space entirely.

If you've ever hit "find all duplicates in an array" or "find the missing number in 1 to n" on LeetCode, this is the same family. Learning the trick once means you can recognize and reuse it across a whole class of problems: missing auto-increment IDs in a database, dropped sequence numbers in a network stream, holes in a bitmap. That generality is exactly why it's worth understanding deeply instead of memorizing.

Problem Overview

You're given an array of unique integers. Originally, those integers formed a complete, contiguous range — every value between some minimum and some maximum was present. Then a few values from the interior of that range were removed. The smallest and largest values are guaranteed to still be in the array; only middle values can be missing.

Your task: return, in sorted order, every value that's missing from that original range. If nothing is missing, return an empty list.

Two things make this different from a generic "find missing number" problem:

• The array isn't sorted 1..n starting at a fixed offset — it can start at any lo and end at any hi.
• Multiple values could theoretically be missing, not just one.

Example

nums = [1, 4, 2, 5]

The values present span from 1 to 5. Walking through 1, 2, 3, 4, 5, everything is there except 3. So the output is:

[3]

A sparser example:

nums = [5, 1]

Here the range is also 1 to 5, but only the endpoints are present. Every interior value — 2, 3, 4 — is missing:

[2, 3, 4]

And a case where nothing is missing:

nums = [7, 8, 6, 9]

The range spans 6 to 9, and all four values are present. Output:

[]

Intuition

The naive instinct is: for every value in the range, check whether it's in nums. That check is a membership test, and without extra structure, a membership test against a list is O(n) — so checking every value in the range makes the whole thing O(n²). The standard fix is to build a hash set from nums first, so each membership check becomes O(1). That gets you O(n) time, but it costs O(n) extra space for the set.

Here's the observation that unlocks the O(1)-extra-space version: because the numbers form a contiguous range, there's a perfect, collision-free mapping between a value and a position. If the range starts at lo, then value num always maps to index num - lo. No hash function, no bucket, no probing — position is identity.

That means you don't need a separate structure to record "have I seen this value." You can record it directly at the corresponding index of a tracker array, using the sign of the number stored there as a visited flag. Initialize tracker[i] = lo + i, so at rest, every slot's value tells you what number belongs there. When you process a value from nums, you flip the sign of the tracker slot at num - lo to negative. At the end, any slot still positive represents a value that was never touched by nums — meaning it's missing.

One detail matters: take abs() of the value at that slot before negating it. Without that, touching an already-negative slot a second time would flip it back positive, silently erasing a mark. Since the problem guarantees uniqueness, no value can route to the same slot twice — but the guard costs nothing and protects you if that assumption ever gets relaxed.

Brute Force Solution

Idea: For each value between lo and hi, check whether it appears in nums.

Algorithm:

1. Determine lo = min(nums) and hi = max(nums).
2. For each v from lo to hi, check v in nums.
3. Collect every v where the check fails.

Advantages: Trivial to write, no risk of off-by-one bugs, obviously correct.

Disadvantages: Each membership check scans the whole array, so this is quadratic.

Complexity: O(n²) time, O(1) extra space (ignoring the output list).

A quick middle-ground improvement: build a set(nums) first, then each membership check is O(1). That gets you to O(n) time but costs O(n) extra space — this is the version most people write first and stop at.

Optimal Solution

The optimal approach keeps O(n) time but reduces the auxiliary space to effectively zero, because the structure you mark in is the same structure you return as output.

Step 1 — Build the tracker. Create an array of size hi - lo + 1, where tracker[i] = lo + i. This is important: size it as hi - lo + 1, not hi - lo — using the wrong size silently drops the last element instead of raising an error.

Step 2 — Mark pass. For every value num in nums, compute its slot index as num - lo. Take the absolute value of whatever is currently in tracker[num - lo], then negate it. This marks that slot as "seen" regardless of whether it was touched before.

Step 3 — Sweep pass. Walk through tracker. Any slot that is still positive was never marked — its value is missing from nums. Collect these into the output list.

Because tracker was built in increasing order and you're filtering it in place, the output comes out sorted for free — no separate sort step needed.

Walkthrough table for nums = [5, 1], range 1–5:

Index	Initial value	After marking 5 and 1
0	1	-1
1	2	2 (untouched → missing)
2	3	3 (untouched → missing)
3	4	4 (untouched → missing)
4	5	-5

Positive survivors: [2, 3, 4] — exactly the missing values.

Python Code

def find_missing_elements(nums: list[int]) -> list[int]:
    """Return every missing value in the contiguous range [min(nums), max(nums)]."""
    lo, hi = min(nums), max(nums)
    tracker = list(range(lo, hi + 1))

    for num in nums:
        idx = num - lo
        tracker[idx] = -abs(tracker[idx])

    return [value for value in tracker if value > 0]

Code Walkthrough

• lo, hi = min(nums), max(nums) — establishes the boundaries of the expected range. These are guaranteed to be present in nums.
• tracker = list(range(lo, hi + 1)) — builds the tracker so tracker[i] = lo + i. Position encodes value; this is the perfect hash.
• idx = num - lo — the change of basis that shifts any range to start at index 0, regardless of what lo actually is.
• tracker[idx] = -abs(tracker[idx]) — marks the slot as visited. abs() first guarantees that touching a slot twice leaves it negative rather than flipping it back to positive.
• [value for value in tracker if value > 0] — the sweep pass. Anything still positive was never marked, meaning it's missing. Order is preserved automatically because tracker was built in increasing order.

Dry Run

nums = [7, 8, 6, 9]

• lo = 6, hi = 9
• tracker = [6, 7, 8, 9]
• Process 7 → idx 1 → tracker[1] = -7
• Process 8 → idx 2 → tracker[2] = -8
• Process 6 → idx 0 → tracker[0] = -6
• Process 9 → idx 3 → tracker[3] = -9
• Final tracker: [-6, -7, -8, -9] — nothing positive.

Result: []. Full coverage of the range naturally produces an empty output with no special-casing.

Complexity Analysis

Time: O(n). The mark pass is one linear scan of nums; the sweep pass is one linear scan of tracker, whose size is bounded by hi - lo + 1.

Space: O(n) for tracker — but tracker is the output buffer, just with sign bits repurposed as visited flags. There's arguably zero space beyond what any correct solution needs to return the answer, since you'd need an array of that size to hold the result regardless.

Why the tracker doesn't beat the hash-set version on big-O: Both approaches are O(n) time and O(n) space. The tracker's advantage is constant factor — no hash computation, no collision handling — not asymptotic class. For most production code, the plain set() version is more obviously correct and the difference is marginal. Reach for the tracker version when you're in a tight loop or a memory-constrained environment where every allocation counts.

Alternative Solutions

Hash set approach:

def find_missing_elements_set(nums: list[int]) -> list[int]:
    lo, hi = min(nums), max(nums)
    seen = set(nums)
    return [v for v in range(lo, hi + 1) if v not in seen]

Same O(n) time, O(n) space. More readable, easier to reason about at a glance, and the natural first answer in an interview. Prefer the tracker version only when you want to demonstrate the in-place technique or when memory truly matters.

Edge Cases

• n = 2 (just lo and hi): Works with no special path — the loop just marks both endpoints and nothing else exists to check.
• Full range with nothing missing: Every tracker slot flips negative; output is [] with no special casing needed.
• Duplicate values (if uniqueness weren't guaranteed): The abs() guard prevents a duplicate touch from un-marking a slot. The problem guarantees uniqueness so this can't trigger here, but it's worth knowing why the guard exists.
• Wrong offset assumption: Hardcoding an offset of 1 instead of computing lo dynamically breaks the moment the range doesn't start at 0 or 1.
• Off-by-one tracker size: Sizing tracker as hi - lo instead of hi - lo + 1 silently truncates the last element.

Common Mistakes

1. Forgetting abs() before negating — causes duplicate values to silently cancel their own mark.
2. Hardcoding the range offset instead of computing lo from the input, which breaks on any range not starting at 0 or 1.
3. Sizing the tracker incorrectly (hi - lo instead of hi - lo + 1), which truncates the last slot without raising any error.
4. Sorting the output unnecessarily — the tracker is already in increasing order, so a comparison-based sort just wastes O(n log n) for nothing.
5. Reaching for a set by default in a memory-constrained context without realizing the array itself can double as the hash structure.
6. Confusing this with "find all duplicates in an array" — the mechanism (sign flipping on index) is identical, but the target of the sweep pass (missing vs. duplicate) is inverted, and mixing them up produces the wrong filter condition.

Interview Questions

• What happens to this algorithm if nums isn't guaranteed unique?
• Can you find all duplicates instead of all missing values using the same tracker technique? What changes in the sweep pass?
• How would you handle negative numbers in the range?
• Can this be adapted to work in a streaming context where you don't have the full array up front?
• What's the tradeoff between the tracker approach and a set() in terms of both correctness confidence and interview communication?

Similar Problems

• Find the Duplicate Number — uses the same index-as-hash idea but flags a repeated touch instead of an absent one.
• Find All Duplicates in an Array — nearly identical mechanism; the sweep pass collects negative slots instead of positive ones.
• First Missing Positive — a tighter variant of the same family, constrained to positions within [1, n].
• Missing Number — the single-missing-value special case of this exact problem.

Key Takeaways

When your data occupies a bounded, contiguous range, the array index itself is a free, collision-free hash function. You can encode "have I seen this" as a property of the array's own contents — via sign, via swapping, via any reversible marking — instead of allocating a separate structure. The technique doesn't change the asymptotic class versus a hash set, but it removes the auxiliary allocation entirely, which matters in memory-constrained or performance-critical contexts. Recognizing when a domain has this bounded-range property is the transferable skill — it shows up far beyond this one problem.

Watch the Video

For the full walkthrough — including the exact mistake made the first time this was coded, and a live dry run of both nums = [5, 1] and nums = [7, 8, 6, 9] — watch the video here: {LINK}

About the Series

This is part of Fun with Learning Technology, a series built around teaching real software engineering intuition — not just memorized solutions. Every video works through the reasoning an experienced engineer actually goes through: why the brute force is tempting, where it breaks down, and how to spot the structural property that unlocks something better. The goal is to build pattern recognition that transfers across problems, not just get one specific LeetCode question checked off.

Call To Action

If this walkthrough helped the trick click, drop a like on the video and subscribe on YouTube so the next one in the series lands in your feed. For deeper written breakdowns like this one, subscribe to the Substack. And if you've hit a variant of this problem in an interview or on the job, share it in the comments — real war stories are the best test cases.

---

def find_missing_elements(nums):
    lo, hi = min(nums), max(nums)
    tracker = list(range(lo, hi + 1))
    for num in nums:
        idx = num - lo
        tracker[idx] = -abs(tracker[idx])
    return [val for val in tracker if val > 0]