algoadvance

Leetcode 2215. Find the Difference of Two Arrays

Problem Statement

Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

• answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
• answer[1] is a list of all distinct integers in nums2 which are not present in nums1.

Each integer in answer[0] and answer[1] must be unique and you may return the answer in any order.

Clarifying Questions

1. Should the output lists contain only unique integers?
   • Yes, all integers in the output lists should be distinct.
2. Can the input arrays contain duplicates?
   • Yes, the input arrays can contain duplicates, but the output lists should only contain unique integers.
3. Is the order of elements in the output important?
   • No, you can return the lists in any order.

Strategy

1. Use sets to keep track of the unique elements from both nums1 and nums2.
2. Traverse through nums1 and add each distinct element to a set.
3. Traverse through nums2 and add each distinct element to a different set.
4. Compute the difference between the two sets:
   • Elements in nums1 not in nums2
   • Elements in nums2 not in nums1
5. Convert these sets to lists and return them.

Code

#include <vector>
#include <unordered_set>
#include <algorithm>

std::vector<std::vector<int>> findDifference(std::vector<int>& nums1, std::vector<int>& nums2) {
    // Create sets to store unique elements of both arrays
    std::unordered_set<int> set1(nums1.begin(), nums1.end());
    std::unordered_set<int> set2(nums2.begin(), nums2.end());

    // Initialize the result vectors
    std::vector<int> res1, res2;
    
    // Find unique elements in nums1 not in nums2
    for (int num : set1) {
        if (set2.find(num) == set2.end()) {
            res1.push_back(num);
        }
    }
    
    // Find unique elements in nums2 not in nums1
    for (int num : set2) {
        if (set1.find(num) == set1.end()) {
            res2.push_back(num);
        }
    }
    
    return {res1, res2};
}

Time Complexity

• Time Complexity: O(n + m)
  • Where n is the length of nums1 and m is the length of nums2.
  • Constructing the sets takes O(n) for set1 and O(m) for set2.
  • The loops that compute the difference also run in O(n) and O(m) respectively.
• Space Complexity: O(n + m)
  • Each set can potentially store all elements from the input arrays.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?