Sponsored
Sponsored
This approach involves using a hash map (or dictionary) to keep track of the frequencies of elements in one of the arrays, then iterating through the second array to identify common elements, decrementing the frequency count accordingly.
Time Complexity: O(n + m), where n and m are the lengths of nums1 and nums2. Space Complexity: O(min(n, m)) due to the counter.
1def intersect(nums1, nums2):
2 from collections import Counter
3 counts = Counter(nums1)
4 intersection = []
5 for num in nums2:
6 if counts[num] > 0:
7 intersection.append(num)
8 counts[num] -= 1
9 return intersectionWe use Python's collections.Counter to track element frequencies in nums1. Then, we iterate through nums2, checking if the current element exists in the counter with a non-zero count: if so, we add the element to the intersection result and decrease its count in the counter.
Another efficient way is to first sort both arrays and then use two pointers to identify intersections. This approach harnesses the ordered nature post-sort to efficiently match elements by moving through both arrays simultaneously.
Time Complexity: O(n log n + m log m) due to sorting of nums1 and nums2. Space Complexity: O(1) extra space is used, aside from the outputs.
1Sort both arrays before iterating. Use indices i and j for navigating nums1 and nums2. Elements are compared, and pointers adjusted accordingly, collecting matching pairs into result.