Find Missing Elements - Solution & Explanation

Problem 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.