3731. Find Missing Elements

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.

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 <= 100
1 <= nums[i] <= 100

Solutions

Solution 1: Hash Table

We first find the minimum and maximum values in the array \(\textit{nums}\), denoted as \(\textit{mn}\) and \(\textit{mx}\). Then we use a hash table to store all elements in the array \(\textit{nums}\).

Next, we iterate through the interval \([\textit{mn} + 1, \textit{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 \(\textit{nums}\).

Python3JavaC++GoTypeScript

class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        mn, mx = min(nums), max(nums)
        s = set(nums)
        return [x for x in range(mn + 1, mx) if x not in s]

class Solution {
    public List<Integer> findMissingElements(int[] nums) {
        int mn = 100, mx = 0;
        Set<Integer> s = new HashSet<>();
        for (int x : nums) {
            mn = Math.min(mn, x);
            mx = Math.max(mx, x);
            s.add(x);
        }
        List<Integer> ans = new ArrayList<>();
        for (int x = mn + 1; x < mx; ++x) {
            if (!s.contains(x)) {
                ans.add(x);
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> findMissingElements(vector<int>& nums) {
        int mn = 100, mx = 0;
        unordered_set<int> s;
        for (int x : nums) {
            mn = min(mn, x);
            mx = max(mx, x);
            s.insert(x);
        }
        vector<int> ans;
        for (int x = mn + 1; x < mx; ++x) {
            if (!s.count(x)) {
                ans.push_back(x);
            }
        }
        return ans;
    }
};

func findMissingElements(nums []int) (ans []int) {
    mn, mx := 100, 0
    s := make(map[int]bool)
    for _, x := range nums {
        mn = min(mn, x)
        mx = max(mx, x)
        s[x] = true
    }
    for x := mn + 1; x < mx; x++ {
        if !s[x] {
            ans = append(ans, x)
        }
    }
    return
}

function findMissingElements(nums: number[]): number[] {
    let [mn, mx] = [100, 0];
    const s = new Set<number>();
    for (const x of nums) {
        mn = Math.min(mn, x);
        mx = Math.max(mx, x);
        s.add(x);
    }
    const ans: number[] = [];
    for (let x = mn + 1; x < mx; ++x) {
        if (!s.has(x)) {
            ans.push(x);
        }
    }
    return ans;
}

3731. Find Missing Elements

Description

Solutions

Solution 1: Hash Table

Comments