3731: Find Missing Elements

Problem Statement

Given an integer array nums of unique integers, find all missing integers in the range between the smallest and largest elements. The smallest and largest elements are guaranteed to be present in the array.

Key Insight

The solution relies on these crucial observations:

1. The smallest and largest elements are always present in the array
2. We only need to check numbers between min and max (inclusive)
3. All integers in the array are unique
4. The range is small (1 to 100), so even O(n²) approaches are efficient

Approach 1: Hash Set (Optimal)

Use a hash set to store all numbers for O(1) lookups, then iterate through the range to find missing numbers.

Algorithm Steps

1. Find the minimum and maximum values in the array
2. Store all numbers in a hash set for fast lookups
3. Iterate from min to max (inclusive)
4. Add numbers not found in the set to the result
5. Return the result list

Complexity Analysis

Linear time for building set and checking range, linear space for the hash set.

class Solution {
public:
    vector<int> findMissingElements(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int minNum = *min_element(nums.begin(), nums.end());
        int maxNum = *max_element(nums.begin(), nums.end());
        
        vector<int> result;
        for (int i = minNum; i <= maxNum; i++) {
            if (numSet.find(i) == numSet.end()) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

import java.util.*;

class Solution {
    public List<Integer> findMissingElements(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        int minNum = Integer.MAX_VALUE;
        int maxNum = Integer.MIN_VALUE;
        
        for (int num : nums) {
            numSet.add(num);
            minNum = Math.min(minNum, num);
            maxNum = Math.max(maxNum, num);
        }
        
        List<Integer> result = new ArrayList<>();
        for (int i = minNum; i <= maxNum; i++) {
            if (!numSet.contains(i)) {
                result.add(i);
            }
        }
        
        return result;
    }
}

class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        num_set = set(nums)
        min_num = min(nums)
        max_num = max(nums)
        
        result = []
        for i in range(min_num, max_num + 1):
            if i not in num_set:
                result.append(i)
                
        return result

Approach 2: Sorting and Linear Scan

Sort the array and then scan through the range to find gaps where numbers are missing.

Algorithm Steps

1. Sort the array in ascending order
2. Find the minimum and maximum values (first and last elements after sorting)
3. Use a pointer to track expected numbers in the range
4. Iterate through sorted array and find missing numbers
5. Return the result list

Complexity Analysis

Sorting dominates time complexity, constant space excluding output.

class Solution {
public:
    vector<int> findMissingElements(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int minNum = nums[0];
        int maxNum = nums.back();
        
        vector<int> result;
        int expected = minNum;
        
        for (int num : nums) {
            while (expected < num) {
                result.push_back(expected);
                expected++;
            }
            expected = num + 1;
        }
        
        return result;
    }
};

import java.util.*;

class Solution {
    public List<Integer> findMissingElements(int[] nums) {
        Arrays.sort(nums);
        int minNum = nums[0];
        int maxNum = nums[nums.length - 1];
        
        List<Integer> result = new ArrayList<>();
        int expected = minNum;
        
        for (int num : nums) {
            while (expected < num) {
                result.add(expected);
                expected++;
            }
            expected = num + 1;
        }
        
        return result;
    }
}

class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        nums.sort()
        min_num = nums[0]
        max_num = nums[-1]
        
        result = []
        expected = min_num
        
        for num in nums:
            while expected < num:
                result.append(expected)
                expected += 1
            expected = num + 1
            
        return result

Approach 3: Boolean Array

Use a boolean array to mark presence of numbers in the range.

Algorithm Steps

1. Find minimum and maximum values
2. Create a boolean array of size (max - min + 1)
3. Mark positions as true for numbers present in the array
4. Collect indices that are false as missing numbers
5. Return the result list

Complexity Analysis

Linear time, space proportional to the range between min and max.

class Solution {
public:
    vector<int> findMissingElements(vector<int>& nums) {
        int minNum = *min_element(nums.begin(), nums.end());
        int maxNum = *max_element(nums.begin(), nums.end());
        int rangeSize = maxNum - minNum + 1;
        
        vector<bool> present(rangeSize, false);
        for (int num : nums) {
            present[num - minNum] = true;
        }
        
        vector<int> result;
        for (int i = 0; i < rangeSize; i++) {
            if (!present[i]) {
                result.push_back(i + minNum);
            }
        }
        
        return result;
    }
};

class Solution {
    public List<Integer> findMissingElements(int[] nums) {
        int minNum = Integer.MAX_VALUE;
        int maxNum = Integer.MIN_VALUE;
        
        for (int num : nums) {
            minNum = Math.min(minNum, num);
            maxNum = Math.max(maxNum, num);
        }
        
        int rangeSize = maxNum - minNum + 1;
        boolean[] present = new boolean[rangeSize];
        
        for (int num : nums) {
            present[num - minNum] = true;
        }
        
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < rangeSize; i++) {
            if (!present[i]) {
                result.add(i + minNum);
            }
        }
        
        return result;
    }
}

class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        min_num = min(nums)
        max_num = max(nums)
        range_size = max_num - min_num + 1
        
        present = [False] * range_size
        for num in nums:
            present[num - min_num] = True
        
        result = []
        for i in range(range_size):
            if not present[i]:
                result.append(i + min_num)
                
        return result

Edge Cases and Testing

1. No Missing Elements

Input: [1,2,3,4,5] → Output: []
Input: [6,7,8,9] → Output: []

2. All Elements Missing Except Ends

Input: [1,5] → Output: [2,3,4]
Input: [10,15] → Output: [11,12,13,14]

3. Single Missing Element

Input: [1,2,4,5] → Output: [3]
Input: [7,8,9,11] → Output: [10]

4. Random Missing Elements

Input: [1,3,5,7,9] → Output: [2,4,6,8]
Input: [2,5,8,11] → Output: [3,4,6,7,9,10]

5. Minimum Array Size

Input: [1,2] → Output: []
Input: [1,3] → Output: [2]

Detailed Explanation

The problem requires finding all integers that are missing between the smallest and largest elements of the array. The key insight is that we only need to consider numbers in the range [min, max] since the endpoints are guaranteed to be present.

For the input [1,4,2,5]:

• Minimum = 1, Maximum = 5
• Expected range: [1,2,3,4,5]
• Present: 1, 2, 4, 5
• Missing: 3

The solution approaches work as follows:

1. Hash Set: Store all numbers in a set for O(1) lookups, then check each number in the range
2. Sorting: Sort the array and find gaps between consecutive elements
3. Boolean Array: Use array indices to mark presence of numbers

All approaches are efficient given the constraints (n ≤ 100, values ≤ 100), but the hash set approach is generally preferred for its simplicity and optimal time complexity.

FAQs