algoadvance

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Clarifying Questions

1. Q: Should the elements in the output be in any specific order? A: No, the elements can be in any order.

2. Q: Can the input arrays contain negative numbers and zeros? A: Yes, the input arrays can contain any integers including negative numbers and zeros.

3. Q: Are the input arrays always non-empty? A: No, they can be empty. If either of the arrays is empty, the output should be an empty array as well.

4. Q: Is it possible for nums1 or nums2 to be very large? A: Yes, it’s possible. Optimized solutions would be preferred for large input sizes.

Strategy

To solve this problem, there are several approaches:

1. Using Hash Maps:
   • Count the frequency of each element in nums1 using a hash map.
   • Iterate through nums2 and for each element, if it exists in the hash map and its count is greater than zero, add it to the result and decrement the count in the hash map.
2. Sorting and Two Pointers:
   • Sort both arrays.
   • Use two pointers to find common elements.

Given the nature of the problem, the hash map approach is preferred because it generally provides a better time complexity for unsorted input arrays.

Code

Here is the implementation in Python using the hash map approach:

from collections import Counter

def intersect(nums1, nums2):
    # Create a counter for nums1
    count1 = Counter(nums1)
    result = []

    # Iterate through nums2
    for num in nums2:
        # If num is in the counter and the count is greater than 0
        if count1[num] > 0:
            result.append(num)
            count1[num] -= 1

    return result

Time Complexity

• Time Complexity: O(m + n), where m is the length of nums1 and n is the length of nums2.
  • Creating the counter for nums1 takes O(m).
  • Iterating through nums2 and managing the count in the hash map also takes O(n).
• Space Complexity: O(min(m, n)) in the worst case where the entire smaller input array could be stored in memory in the form of a counter.

Try our interview co-pilot at AlgoAdvance.com

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