Problem Description
Given two arrays of integers, return an array that represents their intersection. Each element in the result must appear as many times as it shows in both arrays, and the order of the result does not matter.
Key Insights
- Use a hash table to count the occurrences of each number in one array.
- Iterate through the second array, and for each number, check if it exists in the hash table with a non-zero count.
- If it does, add the number to the result and decrement the count in the hash table.
- For sorted arrays, a two-pointer approach can be used for optimal performance.
- Consider memory-efficient methods when one of the arrays is too large to fit in memory.
Space and Time Complexity
Time Complexity: O(n + m), where n and m are the lengths of the two arrays. Space Complexity: O(min(n, m)), since the hash table stores counts for the smaller array.
Solution
We solve the problem by first storing the frequency of each element from one input array using a hash table (dictionary). Then, we iterate through the second array and check if the element is present in the hash table with a positive count. If it is, we add it to the result array and reduce the count. This ensures that each common element is added as many times as it appears in both arrays. If the arrays are sorted, a two-pointer technique can be used where both arrays are traversed simultaneously, providing an alternative approach with potentially lower overhead in specific scenarios.