{x}
blog image

Intersection of Two Arrays II

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:

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]
Explanation: [9,4] is also accepted.

 

Constraints:

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

 

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1's size is small compared to nums2's size? Which algorithm is better?
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solution Explanation: Intersection of Two Arrays II

This problem asks us to find the intersection of two arrays, nums1 and nums2, where the result should include elements that appear in both arrays with their corresponding frequencies. For example, if nums1 = [1, 2, 2, 1] and nums2 = [2, 2], the output should be [2, 2].

The most efficient solution utilizes a hash table (or dictionary in Python) to achieve a time complexity of O(m + n), where 'm' and 'n' are the lengths of nums1 and nums2 respectively. This is significantly better than nested loop approaches which would result in O(m*n) time complexity.

Approach: Using a Hash Table

  1. Count Occurrences: We first create a hash table (e.g., cnt in the code examples) to store the frequency of each element in nums1. The keys are the elements from nums1, and the values are their counts.

  2. Iterate and Compare: We then iterate through nums2. For each element x in nums2, we check if it exists as a key in cnt.

  3. Append to Result: If x is found in cnt and its count (cnt[x]) is greater than 0, it means this element exists in both arrays. We append x to the result array (ans) and decrement cnt[x] to account for the fact that we've found one instance of this element in the intersection.

  4. Return Result: Finally, we return the ans array which contains the intersection elements with their correct frequencies.

Time and Space Complexity Analysis

  • Time Complexity: O(m + n) - We iterate through nums1 once to populate the hash table (O(m)) and then iterate through nums2 once to check for intersections (O(n)). Hash table lookups are considered O(1) on average.

  • Space Complexity: O(min(m, n)) - In the worst case, the hash table will store all unique elements from the smaller array. If one array is significantly smaller than the other, the space complexity approaches O(smaller array size).

Code Examples (with explanations):

The provided code examples in various languages (Python, Java, C++, Go, TypeScript, Rust, Javascript, C#, PHP) all follow the same fundamental approach. The key difference lies in the syntax and data structures used in each language. For example:

  • Python: Uses collections.Counter for efficient counting of elements.
  • Java: Uses an integer array cnt as a hash table (since we know the range of elements is 0-1000). It uses ArrayList for dynamic result array and then converts it to an int[] for return.
  • C++: Uses unordered_map for the hash table.
  • Go: Uses a map for the hash table.
  • Other Languages: Adapt the hash table and other data structures specific to each language, but the core logic remains the same.

The code is generally well-optimized and clearly written, reflecting the described algorithm efficiently. The use of hash tables makes this solution both efficient and readable.