3731. Find Missing Elements

EasyArrayHash TableSorting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums consisting of unique integers.

Originally, nums contained every integer within a certain range. However, some integers might have gone missing from the array.

The smallest and largest integers of the original range are still present in nums. In other words, the boundaries of the range are defined by min(nums) and max(nums), and these two values are guaranteed to exist in the array.

Your task is to find all the integers that should appear within this range but are absent from nums. Specifically, you need to look at every integer between the minimum value and the maximum value (exclusive of the boundaries, since they are always present) and determine which ones are missing.

Return a sorted list of all the missing integers in this range. If no integers are missing, return an empty list.

Example:

If nums = [1, 2, 4, 6], the range spans from 1 to 6. The integers 3 and 5 are missing, so the answer is [3, 5].
If nums = [1, 2, 3], the range spans from 1 to 3 with no gaps, so the answer is [].

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Putting all elements in a hash set enables O(1) membership checks while iterating over the range between min and max.

Open in Flowchart

Intuition

The key insight is that the original range is fully defined by two values: the smallest and the largest integers in nums. Since the problem guarantees that both boundaries are still present in the array, we can simply compute them using min(nums) and max(nums).

Once we know the range [min, max], we understand that originally every integer in this interval should have been present. So a number is "missing" if and only if it lies strictly between the minimum and maximum but does not appear in nums.

This naturally leads us to think about two things:

What numbers should exist? Every integer in the interval [mn + 1, mx - 1]. We exclude the boundaries themselves because they are guaranteed to be present and can never be missing.
How do we quickly check whether a number is present? If we scan the array for each candidate, that would be slow. Instead, we put all elements of nums into a hash set, which allows us to check membership in O(1) time.

With these two pieces in place, the approach becomes straightforward: walk through every integer x in the range [mn + 1, mx - 1], and for each one, ask the set "are you here?". If x is not in the set, it is a missing number and we add it to the answer.

Because we iterate from small to large, the resulting list is automatically sorted, so no extra sorting step is needed.

Pattern Learn more about Sorting patterns.

Solution Approach

Solution 1: Hash Table

We first find the minimum and maximum values in the array nums, denoted as mn and mx. These two values define the boundaries of the original range:

mn, mx = min(nums), max(nums)

Then we use a hash table (a set in Python) to store all elements in the array nums. This lets us check whether any given integer is present in O(1) time:

s = set(nums)

Next, we iterate through the interval [mn + 1, mx - 1]. We exclude mn and mx themselves because they are guaranteed to be present and can never be missing. For each integer x in this range, if x is not in the hash table, we add it to the answer list:

return [x for x in range(mn + 1, mx) if x not in s]

Note that range(mn + 1, mx) covers exactly the integers from mn + 1 up to mx - 1, since the upper bound of range is exclusive.

Because we walk through the range from the smallest value to the largest, the resulting list is naturally sorted, requiring no additional sorting step.

Complexity Analysis:

Time complexity: O(n + m), where n is the length of nums and m is the size of the range [mn, mx]. Building the set takes O(n), and iterating over the range while checking membership takes O(m).
Space complexity: O(n), for the hash table storing all elements of nums. The output list is not counted as extra space.

Example Walkthrough

Let's trace through the algorithm using the small example nums = [1, 2, 4, 6].

Step 1: Find the boundaries of the range.

We compute the minimum and maximum of the array:

mn = min(nums) = 1
mx = max(nums) = 6

So the original range was [1, 6]. Every integer from 1 to 6 should have been present.

Step 2: Build the hash set for fast lookups.

We put all elements of nums into a set:

s = {1, 2, 4, 6}

Now we can check whether any number exists in O(1) time.

Step 3: Walk through the interior of the range.

We iterate over range(mn + 1, mx), which is range(2, 6) — that is, the integers 2, 3, 4, 5. We skip the boundaries 1 and 6 because they are guaranteed to be present.

For each candidate x, we ask the set "are you here?":

`x`	Is `x` in `s = {1, 2, 4, 6}`?	Action
`2`	Yes	Skip
`3`	No	Add `3` to the answer
`4`	Yes	Skip
`5`	No	Add `5` to the answer

Step 4: Return the result.

Since we walked from the smallest value to the largest, the collected numbers are already in sorted order:

Answer: [3, 5]

This matches the expected output. Note that no extra sorting was needed — the natural left-to-right iteration guarantees the result is sorted.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def findMissingElements(self, nums: List[int]) -> List[int]:
6        # Determine the smallest and largest values in the array
7        min_value, max_value = min(nums), max(nums)
8
9        # Build a set for O(1) membership checks
10        num_set = set(nums)
11
12        # Collect every integer strictly between min and max
13        # that is absent from the original array
14        return [
15            value
16            for value in range(min_value + 1, max_value)
17            if value not in num_set
18        ]
19

1class Solution {
2    public List<Integer> findMissingElements(int[] nums) {
3        // Initialize min to a large value and max to a small value
4        // so they get correctly updated during iteration
5        int min = Integer.MAX_VALUE;
6        int max = Integer.MIN_VALUE;
7
8        // Use a set to record all numbers present in the input array
9        Set<Integer> seen = new HashSet<>();
10
11        // First pass: determine the minimum, maximum, and populate the set
12        for (int num : nums) {
13            min = Math.min(min, num);
14            max = Math.max(max, num);
15            seen.add(num);
16        }
17
18        // Collect every value strictly between min and max
19        // that does not appear in the input array
20        List<Integer> result = new ArrayList<>();
21        for (int value = min + 1; value < max; value++) {
22            if (!seen.contains(value)) {
23                result.add(value);
24            }
25        }
26
27        return result;
28    }
29}
30

1class Solution {
2public:
3    vector<int> findMissingElements(vector<int>& nums) {
4        // Track the minimum and maximum values seen in the input.
5        // Initialize minValue high and maxValue low so the first
6        // comparisons correctly update them.
7        int minValue = INT_MAX;
8        int maxValue = INT_MIN;
9
10        // Store every element in a hash set for O(1) average lookups.
11        unordered_set<int> seen;
12        for (int value : nums) {
13            minValue = min(minValue, value);
14            maxValue = max(maxValue, value);
15            seen.insert(value);
16        }
17
18        // Collect every integer strictly between minValue and maxValue
19        // that does not appear in the input.
20        vector<int> result;
21        for (int value = minValue + 1; value < maxValue; ++value) {
22            if (!seen.count(value)) {
23                result.push_back(value);
24            }
25        }
26
27        return result;
28    }
29};
30

1/**
2 * Finds all integers that are missing within the inclusive range
3 * bounded by the minimum and maximum values of the input array.
4 *
5 * @param nums - The array of numbers to inspect.
6 * @returns An array of the missing integers, in ascending order.
7 */
8function findMissingElements(nums: number[]): number[] {
9    // Track the minimum and maximum values seen in the array.
10    // Initialized to sentinel values (min high, max low) so the
11    // first comparisons always update them correctly.
12    let minValue = 100;
13    let maxValue = 0;
14
15    // Store every value present in the array for O(1) membership checks.
16    const seen = new Set<number>();
17
18    // Single pass to compute the bounds and populate the lookup set.
19    for (const value of nums) {
20        minValue = Math.min(minValue, value);
21        maxValue = Math.max(maxValue, value);
22        seen.add(value);
23    }
24
25    // Collect every integer strictly between minValue and maxValue
26    // that does not appear in the original array.
27    const result: number[] = [];
28    for (let value = minValue + 1; value < maxValue; ++value) {
29        if (!seen.has(value)) {
30            result.push(value);
31        }
32    }
33
34    return result;
35}
36

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

Computing min(nums) and max(nums) each takes O(n) time.
Building the set s from nums takes O(n) time.
The list comprehension iterates over the range from mn + 1 to mx, performing an O(1) set lookup for each element. The size of this range is bounded by the spread of values, which is at most O(n) given the values are within a range proportional to the array length.

Combining these, the overall time complexity is O(n).

Space Complexity: O(n), where n is the length of the array nums.

The set s stores up to n elements, requiring O(n) space.
The output list of missing elements requires up to O(n) space.

Thus, the overall space complexity is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Sorting the array before finding min and max (unnecessary overhead)

A common mistake is to sort nums first, assuming the input is unordered and that sorting is needed to identify the boundaries or to keep the output ordered:

# Inefficient approach
class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        nums.sort()  # Unnecessary O(n log n) cost
        min_value, max_value = nums[0], nums[-1]
        num_set = set(nums)
        return [v for v in range(min_value + 1, max_value) if v not in num_set]

Why it's a problem: Sorting adds an O(n log n) cost that buys you nothing. You only need the minimum and maximum, both obtainable in a single O(n) pass via min() and max(). The output is naturally sorted because we iterate over range(min + 1, max) in increasing order — the input order is irrelevant.

Solution: Use min(nums) and max(nums) directly and rely on the range iteration to produce sorted output, as in the original solution.

Pitfall 2: Off-by-one errors with the range boundaries

It's easy to get the boundary conditions wrong and accidentally include min_value and max_value in the result, or miss the integer just below max_value:

# Wrong: includes the boundaries, which are guaranteed present
return [v for v in range(min_value, max_value + 1) if v not in num_set]

# Wrong: misses max_value - 1 if it happens to be absent
return [v for v in range(min_value + 1, max_value - 1) if v not in num_set]

Why it's a problem: The boundaries min_value and max_value are guaranteed to exist and must be excluded from consideration. Meanwhile, max_value - 1 is a valid interior value that could be missing and must be checked.

Solution: Use range(min_value + 1, max_value). The +1 skips the minimum, and because range's upper bound is exclusive, the iteration stops at max_value - 1, correctly excluding the maximum while still checking everything in between.

Pitfall 3: Using a list instead of a set for membership checks

Checking if value not in nums against the raw list looks harmless but degrades performance badly:

# Slow: each "in" check is O(n)
return [v for v in range(min_value + 1, max_value) if v not in nums]

Why it's a problem: Membership testing on a list is O(n). Running it for every value in the range turns the overall time complexity into O(n · m), which can time out on large inputs.

Solution: Convert nums to a set once up front. Set membership testing is average O(1), keeping the total time at O(n + m).

Pitfall 4: Mishandling the no-gap / single-boundary case

Some implementations special-case "no missing elements" or worry about empty results:

# Over-engineered
result = [...]
if not result:
    return []   # redundant — the comprehension already yields []
return result

Why it's a problem: When nums = [1, 2, 3], range(2, 3) yields just 2, which is in the set, so the comprehension naturally returns []. If nums has only two consecutive values like [5, 6], range(6, 6) is empty and also returns []. No special casing is required.

Solution: Trust the list comprehension — it correctly returns an empty list when there are no gaps, with no extra checks needed.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering