Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.
Constraints:
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
My Solution
We can solve this problem by capturing the counts of each element in nums1 and nums2 with two HashMaps. We then iterated through the nums1 HashMap and we for each element in the nums1 HashMap that is also in the nums2 HashMap, we add that element to a list. We add the minimum count between the nums1 count for that element and the nums2 count for that element. So for example if the number 1 occurred in nums1 5 times and it occurred in nums2 3 times, we add 3 instance of 1 to our output list. Finally the problem expects the answer in an integer array, not a list so we just copy those elements to our output array.
Time complexity is O(m+n) to capture the counts of all the elements in nums1 and nums2. Space complexity is also O(m+n) to maintain the two HashMaps and the output list and array.
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer,Integer> nums1_counts = new HashMap<>();
Map<Integer,Integer> nums2_counts = new HashMap<>();
List<Integer> list = new ArrayList<>();
for (int num : nums1) {
nums1_counts.put(num, nums1_counts.getOrDefault(num,0)+1);
}
for (int num : nums2) {
nums2_counts.put(num, nums2_counts.getOrDefault(num,0)+1);
}
for (int num : nums1_counts.keySet()) {
if (nums2_counts.containsKey(num)) {
int cnt = Math.min(nums1_counts.get(num), nums2_counts.get(num));
for (int i = 0; i < cnt; i++) {
list.add(num);
}
}
}
int[] out = new int[list.size()];
for (int i = 0; i < out.length; i++) {
out[i] = list.get(i);
}
return out;
}
}