algoadvance

Leetcode 350. Intersection of Two Arrays II

Problem Statement

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays, and you may return the result in any order.

Example:

  1. Example 1:
    • Input: nums1 = [1,2,2,1], nums2 = [2,2]
    • Output: [2,2]
  2. Example 2:
    • Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    • Output: [4,9]

Constraints:

Clarifying Questions

  1. Are the arrays always non-empty?
    • Yes, given the constraints, each array has at least one element.
  2. Is the result unique, or can there be multiple valid outputs?
    • The result is not unique; elements can be returned in any order as long as the correct count of each element is maintained.
  3. Can we use extra space for our solution?
    • Yes, using extra space such as hash maps is acceptable for this problem.
  4. How should we handle cases where elements in nums1 or nums2 do not have overlaps?
    • The result should only include elements that appear in both arrays.

Strategy

  1. Use a hash map (unordered_map) to count the occurrences of each element in nums1.
  2. Iterate through nums2, and for each element, if the element exists in the hash map and its count is greater than zero, add it to the result and decrement its count in the hash map.
  3. Convert the result list to a vector to match the expected return type.

Time Complexity

Code

#include <vector>
#include <unordered_map>

std::vector<int> intersect(std::vector<int>& nums1, std::vector<int>& nums2) {
    std::unordered_map<int, int> countMap;
    for (int num : nums1) {
        countMap[num]++;
    }
    
    std::vector<int> intersection;
    for (int num : nums2) {
        if (countMap[num] > 0) {
            intersection.push_back(num);
            countMap[num]--;
        }
    }
    
    return intersection;
}

Explanation

  1. Create a hash map countMap to store the count of each element in nums1.
  2. Traverse through nums1 and populate the countMap.
  3. Create a vector intersection to store the result.
  4. Traverse through nums2, for each element, check if it exists in countMap with a count greater than 0:
    • If yes, add the element to intersection and decrement the count in countMap.
  5. Return the intersection vector as the result.

This solution ensures that we only include elements in the result the number of times they appear in both nums1 and nums2, and it uses efficient operations with a hash map for fast lookups and updates.

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