Welcome to Subscribe On Youtube

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}$.

• Java
• C++
• Python
• Go
• TypeScript

• 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;
      }
  };
  
  

• 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]
  
  

• 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;
  }
  
  

All Problems

All Solutions