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.
1import java.util.*;
2
3public class Solution {
4 public int[] intersect(int[] nums1, int[] nums2) {
5 Map<Integer, Integer> map = new HashMap<>();
6 List<Integer> result = new ArrayList<>();
7 for (int num : nums1) {
8 map.put(num, map.getOrDefault(num, 0) + 1);
9 }
10 for (int num : nums2) {
11 if (map.getOrDefault(num, 0) > 0) {
12 result.add(num);
13 map.put(num, map.get(num) - 1);
14 }
15 }
16 return result.stream().mapToInt(i -> i).toArray();
17 }
18}Java's HashMap is used for frequency counting of nums1. We then iterate through nums2, checking against the frequency map: if the element is found with a positive count, we add it to the result list and decrease its count 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.
1
Sorting is applied using C's qsort. Two pointers scan through both sorted arrays to identify matching elements, storing such matches. stdlib.h qsort is vital for sort functionality.