Find Missing Elements — 🟡 Intermediate (2/3) — LeetCode Daily Python Solution (index as hash trick)

Introduction

Missing-number problems look harmless the first time you see them, and that's exactly why they're dangerous in an interview. The naive solution is obvious — loop through a range, check membership, done. But interviewers rarely care whether you can solve it; they care whether you can solve it well, and "well" here means recognizing that a plain list lookup is O(n) per check, that a set fixes the speed problem but costs memory, and that there's a third option most candidates never consider: using the array itself as a hash table.

This pattern — index as hash, sign as a visited flag — shows up far beyond LeetCode. Database engineers use it to spot missing sequential IDs. Backend teams use variations of it to catch skipped invoice numbers or dropped packets in a stream. Once you've internalized it, you'll start noticing "find the gap in a sequence" problems everywhere, and you'll reach for the in-place trick instead of instinctively reaching for a set.

By the end of this article, you'll understand not just how to write the optimal solution, but why it works, when it's worth the extra complexity over a simple set-based approach, and the one classic off-by-one bug that trips up almost everyone who tries it.

Problem Overview

You're given an array of unique integers. At some point in the past, this array held every integer in a contiguous range — from its smallest value to its largest value, with no gaps. Since then, some numbers from the middle of that range have been removed. The smallest and largest values are guaranteed to still be present.

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

Two guarantees make this problem tractable:

• All values in the input are unique — no duplicate handling needed.
• The minimum and maximum of the range are always present in the array, so you never have to guess the range boundaries — you can derive them directly with min() and max().

Example

Input: [1, 4, 2, 5]

The smallest value is 1, the largest is 5, so the complete range should be [1, 2, 3, 4, 5]. Checking each value against the input array:

Value	In array?
1	Yes
2	Yes
3	No
4	Yes
5	Yes

Output: [3]

Second example — nothing missing: [7, 8, 6, 9]. The range is 6 through 9, and every value in that range appears in the array. Output: [].

Intuition

Start with the most literal reading of the problem: "for every number in the range, check if it's in the array." That's a correct algorithm — the question is how you implement the "check if it's in the array" step.

A plain Python list makes membership checks slow, because in on a list is a linear scan — you're back to nested loops and O(n × range) behavior. The standard fix is to drop the array into a set, which gives O(1) average-case lookups. That's a completely reasonable answer, and for most real-world code, it's the one you should actually ship.

But there's a subtler idea worth knowing: you don't need a separate structure to remember "have I seen this value" — you can encode that information directly into an array you were going to build anyway. If you create a tracker array that represents the full range (lo to hi), then each value's position in that array can double as a "have I seen it" flag. Instead of asking a hash set "have I seen this," you compute the value's slot directly and flip a sign there. No lookup, no hashing overhead — you jump straight to the answer.

This only works because of two things the problem guarantees: values are unique (so no slot gets fought over) and bounded to a known range (so every value maps cleanly to a slot).

Brute Force Solution

Idea: For every integer from lo to hi, check whether it exists in nums.

Algorithm:

1. Compute lo = min(nums) and hi = max(nums).
2. Convert nums to a set for fast lookups.
3. Iterate through the range lo to hi, collecting any value not found in the set.

Advantages:

• Extremely easy to read and reason about.
• Obviously correct — there's no clever indexing to get wrong.
• Fast to write in an interview when you're under time pressure.

Disadvantages:

• Requires an auxiliary set, which costs O(n) extra memory beyond the output.
• If you skip the set and check membership directly against the list, you get O(n × range) time — a real performance trap for larger inputs.

Time complexity: O(n) with a set (O(n × range) without one). Space complexity: O(n) for the set.

Optimal Solution

The optimized version replaces the set with a tracker array that is the range itself, and uses sign flipping to mark presence in place.

Step by step:

1. Find lo = min(nums) and hi = max(nums).
2. Build tracker = list(range(lo, hi + 1)) — this is both your working structure and the eventual shape of your answer.
3. For every number in nums, compute its offset: idx = num - lo. This tells you exactly which slot in tracker corresponds to that number.
4. Flip the sign at tracker[idx] to negative, using abs() first so a slot never gets un-flipped if a value's offset happens to be hit twice conceptually (it won't with unique values, but abs() makes the operation idempotent and safe).
5. After the marking pass, scan tracker. Any slot still positive was never touched by a real value — meaning that number is missing.
6. Filter for positive values with a list comprehension. Since tracker was built in ascending order, the result comes out sorted automatically.

Visualizing it for [1, 4, 2, 5]:

Slot (index)	Represents	Marked by	Final sign
0	1	1 → flipped	negative
1	2	2 → flipped	negative
2	3	nobody	positive
3	4	4 → flipped	negative
4	5	5 → flipped	negative

Slot 2 stays positive — that's your missing number, 3.

Python Code

def find_missing_elements(nums: list[int]) -> list[int]:
    if not nums:
        return []

    lo, hi = min(nums), max(nums)
    tracker = list(range(lo, hi + 1))

    # Pass 1: mark every value that's present by flipping its slot negative
    for num in nums:
        idx = num - lo
        tracker[idx] = -abs(tracker[idx])

    # Pass 2: whatever is still positive was never marked, i.e. missing
    return [val for val in tracker if val > 0]

Code Walkthrough

• if not nums: return [] — guards against an empty input; there's no range to check.
• lo, hi = min(nums), max(nums) — the problem guarantees these are the true boundaries of the original range.
• tracker = list(range(lo, hi + 1)) — builds the full expected range. Note the + 1: the range is inclusive of hi, so the tracker needs hi - lo + 1 elements, not hi - lo.
• idx = num - lo — converts an actual value into its position in tracker. This is the line that trips people up (more below).
• tracker[idx] = -abs(tracker[idx]) — flips the value at that slot negative. Using abs() first guarantees the flip is always negative, regardless of the slot's current sign.
• The final list comprehension keeps only values that are still positive — the untouched, missing ones — and returns them in the same ascending order tracker was built in.

Dry Run

Input: [5, 1]

1. lo = 1, hi = 5.
2. tracker = [1, 2, 3, 4, 5].
3. Mark 5: idx = 5 - 1 = 4 → tracker[4] = -5 → tracker = [1, 2, 3, 4, -5].
4. Mark 1: idx = 1 - 1 = 0 → tracker[0] = -1 → tracker = [-1, 2, 3, 4, -5].
5. Scan for positives: 2, 3, 4.

Output: [2, 3, 4] — exactly the numbers missing between 1 and 5.

Complexity Analysis

Time: O(n), where n is hi - lo + 1 (the size of the full range). Both passes — marking and scanning — are single linear walks with no nested loops or lookups, so the total work scales directly with the range size.

Space: O(n) for tracker, but this is the answer taking shape, not overhead on top of it — you were always going to need to produce output roughly this size. Compared to the brute-force approach, you eliminate the separate hash set entirely, so there's no additional structure beyond what the output requires.

Alternative Solutions

The honest alternative is the set-based brute force shown earlier — three or four lines, trivially readable, and obviously correct at a glance. In real production code, that's usually the right call: the tracker trick only earns its keep when you specifically care about shaving off the memory a hash set would cost. For a quick script or a one-off data check, reach for the set every time.

Edge Cases

• Empty input: handled explicitly, returns [].
• No missing numbers: every slot in tracker gets flipped, so the final comprehension returns [].
• Smallest possible valid input: an array with just [lo, hi] — two elements — still works correctly since the tracker still builds the full range between them.
• lo far from zero (e.g., 50 instead of 1): works correctly only if you subtract lo before indexing — this is the classic bug (see below).
• Duplicates: not a concern here, since the problem guarantees unique values.

Common Mistakes

1. Indexing with the raw value instead of the offset. Writing tracker[num] instead of tracker[num - lo] works by coincidence when lo is 1, and breaks silently or with an IndexError the moment lo is anything else.
2. Off-by-one in the tracker size. Using range(lo, hi) instead of range(lo, hi + 1) drops the last element of the range and produces a mangled tracker.
3. Forgetting abs() before flipping the sign. Without it, repeated logic paths can double-flip a slot back to positive, silently corrupting the result.
4. Assuming a set-based lookup and an index-based lookup have the same complexity trade-offs. They don't — one trades memory for simplicity, the other trades a bit of clarity for zero extra space.
5. Checking membership against a raw list instead of a set in the brute-force version. This quietly turns an O(n) solution into O(n × range), which won't show up on small inputs but will wreck performance on large ones.

Interview Questions

• What's the time and space complexity of your solution, and how would it change if lo and hi weren't guaranteed to be in the array?
• How would you modify this if the array could contain duplicates?
• Could you solve this without building the tracker array at all, using only the sign of nums itself?
• What happens if the range is extremely large but the array is sparse — does this approach still make sense?
• How would you extend this to report missing ranges instead of individual missing numbers?

Similar Problems

• Find All Numbers Disappeared in an Array (LeetCode 448) — nearly identical in-place sign-flip technique, applied to a 1 to n range instead of an arbitrary lo to hi range.
• First Missing Positive (LeetCode 41) — another in-place indexing trick, this time using swaps instead of sign flips to achieve O(1) space.
• Missing Number (LeetCode 268) — a simpler variant solvable with math (sum formula) or XOR, good for contrasting arithmetic tricks against the hashing trick.
• Set Mismatch (LeetCode 645) — combines "find missing" with "find duplicate," a natural extension of the sign-marking idea.

Key Takeaways

The core lesson isn't the code — it's the pattern: when values map cleanly onto a bounded range, you can use the array itself as a hash table by treating index as key and sign as a visited flag. That eliminates the need for a separate set entirely. The set-based solution is still the right default for readability; reach for the in-place trick only when memory is genuinely tight and you're comfortable with the added indexing complexity.

Watch the Video

Prefer to see the sign flips happen live, one slot at a time? Watch the full walkthrough here: {LINK}

About the Series

This breakdown is part of Fun with Learning Technology, a daily series working through LeetCode problems the way you'd actually want them explained — building intuition first, writing clean Python second, and calling out the exact line where most people get tripped up.

Call To Action

If this cleared up the index-as-hash trick for you, drop a like on the video and subscribe on YouTube — new daily problems drop every day. For deeper write-ups like this one delivered straight to your inbox, subscribe to the Substack. And if you've hit this pattern in a real system (missing IDs, dropped packets, whatever), share it in the comments — I read every one.

---

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]