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.
Return a sorted list of all the missing integers in this range. If no integers are missing, return an empty list.
Example 1:
Input: nums = [1,4,2,5]
Output: [3]
Explanation:
The smallest integer is 1 and the largest is 5, so the full range should be [1,2,3,4,5]. Among these, only 3 is missing.
Example 2:
Input: nums = [7,8,6,9]
Output: []
Explanation:
The smallest integer is 6 and the largest is 9, so the full range is [6,7,8,9]. All integers are already present, so no integer is missing.
Example 3:
Input: nums = [5,1]
Output: [2,3,4]
Explanation:
The smallest integer is 1 and the largest is 5, so the full range should be [1,2,3,4,5]. The missing integers are 2, 3, and 4.
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 100Problem Overview: You receive an array containing numbers from a defined range, but some values are missing. The task is to identify which elements from the expected range do not appear in the array.
Approach 1: Sorting and Linear Scan (Time: O(n log n), Space: O(1) or O(n))
Sort the array first, then iterate through it while tracking the expected sequence of numbers. Whenever the current value is greater than the expected number, all numbers in between are missing. This approach works because sorting places elements in ascending order, allowing a single pass to detect gaps. Sorting adds an O(n log n) cost, but the scanning step itself is O(n). This technique is useful when the array can be safely reordered and you prefer avoiding extra hash structures.
Approach 2: Hash Table Lookup (Time: O(n), Space: O(n))
Store all elements from the array in a hash set. Then iterate through the expected range of values and check whether each number exists in the set. Missing elements are those that fail the membership check. Hash lookups run in average O(1) time, so the entire process becomes O(n). This approach is straightforward and efficient because it separates presence tracking from detection logic. It relies on constant-time membership checks provided by a Hash Table.
Approach 3: Boolean Marker Array (Time: O(n), Space: O(n))
Create a boolean array of size equal to the expected range. Traverse the input array and mark the index corresponding to each value as present. After marking, iterate through the marker array to collect indices that remain unmarked. Those indices represent missing numbers. This method behaves similarly to a hash set but replaces hashing with direct indexing. It works best when the range of numbers is small and contiguous, a common scenario in Array problems.
Recommended for interviews: The hash table approach is usually the expected solution. It demonstrates understanding of constant-time lookups and clean separation between data storage and verification. Interviewers may accept the Sorting approach as a first step because it clearly shows how gaps reveal missing values, but the O(n) hash-based solution signals stronger algorithmic intuition.
We first find the minimum and maximum values in the array nums, denoted as mn and mx. Then we use a hash table to store all elements in the array nums.
Next, we iterate through the interval [mn + 1, mx - 1]. For each integer x, if x is not in the hash table, we add it to the answer list.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Scan | O(n log n) | O(1) or O(n) | When modifying or sorting the array is acceptable and simplicity matters |
| Hash Table | O(n) | O(n) | General case with unsorted arrays where fast lookups are needed |
| Boolean Marker Array | O(n) | O(n) | When the value range is known and small enough for direct indexing |
3731. Find Missing Elements (Leetcode Easy) • Programming Live with Larry • 376 views views
Watch 6 more video solutions →Practice Find Missing Elements with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor