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.
1#include <vector>
2#include <unordered_map>
3
4std::vector<int> intersect(std::vector<int>& nums1, std::vector<int>& nums2) {
5 std::unordered_map<int, int> counts;
6 std::vector<int> result;
7 for (int num : nums1) counts[num]++;
8 for (int num : nums2) {
9 if (counts[num] > 0) {
10 result.push_back(num);
11 counts[num]--;
12 }
13 }
14 return result;
15}Utilizes C++'s unordered_map to maintain element counts from nums1. Then iterates nums2 to find intersections, adding them to the result while decrementing counts in the map.
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.
1using System.Collections.Generic;
public class Solution {
public int[] Intersect(int[] nums1, int[] nums2) {
Array.Sort(nums1);
Array.Sort(nums2);
List<int> result = new List<int>();
int i = 0, j = 0;
while (i < nums1.Length && j < nums2.Length) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
result.Add(nums1[i]);
i++;
j++;
}
}
return result.ToArray();
}
}Initial sorting sets the stage for comparing nums1 and nums2 with twin indices. Matching elements direct appends to result collection.