Intersection of Two Arrays II (Hash Map)

To solve the intersection of two arrays where duplicates matter, I would prioritize an approach that ensures linear time complexity while accurately tracking frequencies. First, I'd clarify that the output should contain each element as many times as it appears in both input arrays. For instance, if '2' appears twice in the first array and three times in the second, the result should include '2' exactly twice. My strategy involves using a Hash Map to store the frequency of elements from the first array. By iterating through the first array, I populate the map where keys are numbers and values are their counts. Next, I iterate through the second array. For every element encountered, I check if it exists in the map with a count greater than zero. If it does, I add it to my result list and decrement the corresponding value in the map. This ensures we only capture the overlapping instances. This approach achieves O(m + n) time complexity, which is optimal since we must examine every element at least once. The space complexity is O(min(m, n)) if we choose to build the map on the smaller array first, optimizing memory usage. This method avoids nested loops, preventing the O(m*n) performance hit, which is crucial for handling large-scale data often seen in Amazon's backend systems.