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.
1function intersect(nums1, nums2) {
2 const map = {};
3 const result = [];
4 for (let num of nums1) {
5 map[num] = (map[num] || 0) + 1;
6 }
7 for (let num of nums2) {
8 if (map[num] > 0) {
9 result.push(num);
10 map[num]--;
11 }
12 }
13 return result;
14}We utilize an object to store frequencies of elements in nums1. While iterating over nums2, if an element exists in the frequency map with a non-zero count, we append it to the result and decrement the frequency count.
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.
1Both arrays are initially sorted, and two pointers i and j iterate from the start of nums1 and nums2 respectively, by comparing elements. If matching, we add to the result; else, movements depend on comparatives.