Find Missing Elements

Difficulty: Easy | Acceptance: 83.10% | Paid: No Topics: Array, Hash Table, Sorting

You are given two integer arrays nums1 and nums2. Return a list of all the elements in nums1 that are not present in nums2.

The result can be returned in any order.

Examples

Example 1:

Input: nums1 = [1,2,3,4,5], nums2 = [2,3,4,5,6]
Output: [1]
Explanation: Only 1 is present in nums1 but not in nums2.

Example 2:

Input: nums1 = [1,2,3], nums2 = [4,5,6]
Output: [1,2,3]
Explanation: All elements of nums1 are missing from nums2.

Example 3:

Input: nums1 = [1,2,2,3], nums2 = [2,3,4]
Output: [1,2]
Explanation: 1 and one occurrence of 2 are missing from nums2.

Constraints

1 <= nums1.length, nums2.length <= 1000
-1000 <= nums1[i], nums2[i] <= 1000

• Hash Set Approach
• Sorting + Two Pointers
• Frequency Map Approach

Hash Set Approach

Intuition Store all elements of nums2 in a hash set for O(1) lookup, then iterate through nums1 to find elements not in the set.

Steps

• Create a hash set from nums2 elements
• Iterate through nums1 and collect elements not in the set
• Return the result list

class Solution:
    def findMissingElements(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums2_set = set(nums2)
        result = []
        for num in nums1:
            if num not in nums2_set:
                result.append(num)
        return result

Complexity

• Time: O(n + m) where n = nums1.length, m = nums2.length
• Space: O(m) for the hash set
• Notes: Fast lookup with hash set, optimal for most cases

Sorting + Two Pointers

Intuition Sort both arrays and use two pointers to find elements in nums1 that don’t have matches in nums2.

Steps

• Sort both arrays
• Use two pointers to traverse both arrays
• When elements match, advance both pointers
• When nums1 element is smaller, it’s missing from nums2
• When nums2 element is smaller, advance nums2 pointer

class Solution:
    def findMissingElements(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        result = []
        i, j = 0, 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                result.append(nums1[i])
                i += 1
            else:
                j += 1
        while i < len(nums1):
            result.append(nums1[i])
            i += 1
        return result

Complexity

• Time: O(n log n + m log m) for sorting
• Space: O(1) extra space (excluding output)
• Notes: Useful when space is constrained, but slower due to sorting

Frequency Map Approach

Intuition Count frequency of elements in nums2, then check each element in nums1 against the frequency map.

Steps

• Create a frequency map from nums2
• Iterate through nums1 and collect elements with zero frequency
• Return the result list

class Solution:
    def findMissingElements(self, nums1: List[int], nums2: List[int]) -> List[int]:
        from collections import Counter
        freq = Counter(nums2)
        result = []
        for num in nums1:
            if freq.get(num, 0) == 0:
                result.append(num)
            else:
                freq[num] -= 1
        return result

Complexity

• Time: O(n + m) where n = nums1.length, m = nums2.length
• Space: O(m) for the frequency map
• Notes: Handles duplicates correctly, similar to hash set approach