3731. Find Missing Elements

Array
Hash Table
Sorting

TIME

O(n + R) (R = max - min)

SPACE

O(n)

Intuition

The original range is exactly [min(nums), max(nums)] (endpoints are guaranteed present). Any value in that range not found in nums is missing.

Approach

Put nums into a set for O(1) membership checks; find lo = min and hi = max.
For every value v in [lo, hi], add it to the answer if it's not in the set.
Iterating in increasing order yields the sorted result directly.

Complexity

Time: O(n + R) where R = max - min
Space: O(n), the membership set

Edge Cases

No missing values (Example 2) → empty list
Only two elements far apart (Example 3) → the whole interior is missing
Consecutive min/max with nothing between → empty list
Values are unique per constraints, so no duplicate handling needed

Code

from typing import List


class Solution:
    def missingElements(self, nums: List[int]) -> List[int]:
        """
        3731. Find Missing Elements
        Time: O(n + R)  (R = max - min)
        Space: O(n)
        """
        present = set(nums)
        lo, hi = min(nums), max(nums)
        return [v for v in range(lo, hi + 1) if v not in present]

import java.util.ArrayList;
import java.util.List;

/**
 * 3731. Find Missing Elements
 * Time: O(n + R)  (R = max - min)
 * Space: O(n)
 */
class Solution {
    public int[] missingElements(int[] nums) {
        boolean[] present = new boolean[101]; // values in [1, 100]
        int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE;
        for (int x : nums) {
            present[x] = true;
            lo = Math.min(lo, x);
            hi = Math.max(hi, x);
        }

        List<Integer> missing = new ArrayList<>();
        for (int v = lo; v <= hi; v++) {
            if (!present[v]) {
                missing.add(v);
            }
        }

        int[] result = new int[missing.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = missing.get(i);
        }
        return result;
    }
}