LeetCode 3731 - Find Missing Elements

LeetCode Problem 3731

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

This problem asks us to reconstruct a missing sequence of integers from a partially incomplete array.

We are given an integer array nums containing unique values, and we know an important fact: the array originally contained every integer in a continuous range, but some numbers were removed. Even though some values are missing, the smallest and largest values of the original range are guaranteed to still exist in the array.

Our task is to return a sorted list of all missing integers between the minimum and maximum numbers in the array.

In simpler terms, we want to:

1. Find the smallest number in nums
2. Find the largest number in nums
3. Generate every integer in that inclusive range
4. Identify which numbers are absent from nums
5. Return those missing numbers in ascending order

For example, if nums = [1,4,2,5], the minimum is 1 and the maximum is 5. The complete original range must have been:

[1,2,3,4,5]

Since 3 is missing from nums, we return:

[3]

The constraints are very small:

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 100
• All integers are unique

These limits tell us that performance is not especially demanding. Even a less efficient solution would likely pass. However, since this is an interview-style problem, we should still think about designing a clean and efficient approach.

Several guarantees simplify the implementation:

• The array always contains at least two numbers.
• Numbers are unique, so we do not need to handle duplicates.
• The smallest and largest values are always present, meaning the range boundaries are reliable.
• The result must be sorted, but iterating from minimum to maximum naturally gives us sorted output.

There are a few edge cases worth recognizing early. If the array already contains every number in the range, we should return an empty list. If the input contains only the minimum and maximum values, then everything in between is missing. Another subtle case is when the array is unsorted, which means we cannot assume the first or last element defines the range.

Approaches

Brute Force Approach

A straightforward approach is to first sort the array, then inspect gaps between consecutive numbers.

After sorting, we compare adjacent values. If the difference between two neighboring numbers is greater than 1, then all integers in between are missing and should be added to the result.

For example:

[1,4,2,5]

After sorting:

[1,2,4,5]

We compare adjacent elements:

• Between 1 and 2, nothing is missing
• Between 2 and 4, number 3 is missing
• Between 4 and 5, nothing is missing

This method works because sorting places numbers in natural order, making gaps easy to identify.

However, sorting introduces an O(n log n) time cost, which is unnecessary because we only care whether numbers exist in a range.

Optimal Approach

The key observation is that we only need to determine whether each integer between the minimum and maximum exists in the array.

A hash set is ideal for fast membership checks.

We first compute:

• minimum = min(nums)
• maximum = max(nums)

Then we place all values into a set for O(1) average lookup time.

Next, we iterate through every integer from minimum to maximum. If a number is not present in the set, we add it to the result.

Since we scan the range in ascending order, the output is automatically sorted.

This avoids sorting entirely and produces a cleaner, more direct solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(1) or O(n)	Sort array and detect gaps between adjacent numbers
Optimal	O(n + r)	O(n)	Use a hash set for constant time membership checks, where r is the range size

Here, r = max(nums) - min(nums).

Algorithm Walkthrough

Optimal Algorithm

1. Find the smallest and largest values in the array.

These define the boundaries of the original continuous range. Since the problem guarantees both are still present, we can safely use them. 2. Convert the array into a hash set.

A set allows constant average time membership checking. Instead of repeatedly scanning the array to see whether a number exists, we can check instantly. 3. Iterate through every integer from the minimum to the maximum value.

This reconstructs the original range one number at a time. 4. For each integer, check whether it exists in the set.

If the number is missing, append it to the result list. 5. Return the result list.

Because we iterate in increasing order, the missing numbers are naturally sorted.

Why it works

The algorithm works because every valid number from the original range must lie between the minimum and maximum values. By checking each integer in this interval exactly once, we guarantee that every missing number is discovered. Since the set contains exactly the numbers present in nums, any value absent from the set must be missing from the original sequence.

Python Solution

from typing import List

class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        minimum = min(nums)
        maximum = max(nums)

        existing_numbers = set(nums)
        missing_numbers = []

        for number in range(minimum, maximum + 1):
            if number not in existing_numbers:
                missing_numbers.append(number)

        return missing_numbers

The implementation begins by identifying the minimum and maximum values in the array. These determine the original range of integers.

Next, we convert nums into a set called existing_numbers. This is important because membership checks in a set are extremely efficient, usually O(1).

We then iterate through every number in the inclusive range [minimum, maximum]. Whenever a number is absent from the set, we add it to missing_numbers.

Finally, we return the result list. Since numbers are checked in increasing order, the output is already sorted and no additional sorting step is necessary.

Go Solution

func findMissingElements(nums []int) []int {
	minimum := nums[0]
	maximum := nums[0]

	// Find minimum and maximum
	for _, num := range nums {
		if num < minimum {
			minimum = num
		}
		if num > maximum {
			maximum = num
		}
	}

	// Build hash set
	existingNumbers := make(map[int]bool)
	for _, num := range nums {
		existingNumbers[num] = true
	}

	// Find missing numbers
	missingNumbers := []int{}

	for number := minimum; number <= maximum; number++ {
		if !existingNumbers[number] {
			missingNumbers = append(missingNumbers, number)
		}
	}

	return missingNumbers
}

The Go implementation follows the same logic as the Python version. Since Go does not have built-in min() and max() functions for slices, we manually scan the array to compute them.

Instead of a Python set, Go uses a map[int]bool to simulate hash set behavior. Presence checking remains efficient with average O(1) lookups.

The result is initialized as an empty slice rather than nil, ensuring a clean empty return value when no integers are missing.

Worked Examples

Example 1

Input:

nums = [1,4,2,5]

First, determine the range:

Variable	Value
minimum	1
maximum	5

Create the set:

{1,2,4,5}

Iterate through the range:

Current Number	In Set?	Result
1	Yes	[]
2	Yes	[]
3	No	[3]
4	Yes	[3]
5	Yes	[3]

Final answer:

[3]

Example 2

Input:

nums = [7,8,6,9]

Range:

Variable	Value
minimum	6
maximum	9

Set:

{6,7,8,9}

Iteration:

Current Number	In Set?	Result
6	Yes	[]
7	Yes	[]
8	Yes	[]
9	Yes	[]

Final answer:

[]

Example 3

Input:

nums = [5,1]

Range:

Variable	Value
minimum	1
maximum	5

Set:

{1,5}

Iteration:

Current Number	In Set?	Result
1	Yes	[]
2	No	[2]
3	No	[2,3]
4	No	[2,3,4]
5	Yes	[2,3,4]

Final answer:

[2,3,4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + r)	Building the set takes O(n), scanning the range takes O(r)
Space	O(n)	The hash set stores all elements from nums

Here, n is the number of elements in nums, and r = max(nums) - min(nums).

The algorithm performs one pass to build the hash set and another pass through the numerical range. Since constraints are small, this is highly efficient. In the worst case, the range is at most 100, making the solution effectively constant time for this problem size.

Test Cases

solution = Solution()

# Provided examples
assert solution.findMissingElements([1, 4, 2, 5]) == [3]  # single missing number
assert solution.findMissingElements([7, 8, 6, 9]) == []  # no missing numbers
assert solution.findMissingElements([5, 1]) == [2, 3, 4]  # only endpoints exist

# Boundary values
assert solution.findMissingElements([1, 2]) == []  # smallest valid input, consecutive
assert solution.findMissingElements([1, 100]) == list(range(2, 100))  # maximum range

# Unsorted input
assert solution.findMissingElements([10, 7, 8, 5]) == [6, 9]  # unordered array

# Missing multiple consecutive numbers
assert solution.findMissingElements([1, 2, 6]) == [3, 4, 5]  # large gap

# Missing one number in middle
assert solution.findMissingElements([2, 4, 3, 6]) == [5]  # single missing value

# Already complete range
assert solution.findMissingElements([3, 4, 5, 6, 7]) == []  # no gaps

# Non-consecutive sparse case
assert solution.findMissingElements([1, 10]) == [2, 3, 4, 5, 6, 7, 8, 9]  # many missing

Test	Why
[1,4,2,5]	Validates a single missing number
[7,8,6,9]	Ensures empty result when range is complete
[5,1]	Tests only endpoints present
[1,2]	Smallest legal input size
[1,100]	Tests maximum possible range
[10,7,8,5]	Confirms unsorted input works correctly
[1,2,6]	Validates multiple consecutive missing numbers
[2,4,3,6]	Checks single missing value in the middle
[3,4,5,6,7]	Verifies already complete range
[1,10]	Tests sparse input with many missing values

Edge Cases

No Missing Numbers

An important edge case occurs when every number between the minimum and maximum already exists.

For example:

[6,7,8,9]

A buggy implementation might mistakenly add values or mishandle an empty result. Our implementation correctly returns an empty list because every membership check succeeds and nothing is appended.

Only Endpoints Present

Another tricky case is when the array contains only the smallest and largest values.

For example:

[1,5]

Everything between them is missing. A careless implementation might fail to include all intermediate numbers or incorrectly assume neighboring values exist. Since our algorithm scans the entire range from minimum to maximum, every absent number is correctly collected.

Unsorted Input

The array is not guaranteed to be sorted.

For example:

[10,7,8,5]

A naive approach that assumes the first and last elements define the range would fail here. Our solution avoids this issue by explicitly computing min(nums) and max(nums), ensuring the correct boundaries regardless of input order.

Large Gaps Between Numbers

Inputs may contain large gaps.

For example:

[1,100]

A weak implementation might become inefficient by repeatedly scanning the array to check existence. Using a hash set guarantees fast lookups even when many values are missing.