[Leetcode][350. Intersection of Two Arrays II] 2 Solutions: Sort with Two Pointers and HashMap

By Long Luo

This article is the solution of Problem 350. Intersection of Two Arrays II.

Solution 1 Sort + Two Pointers

Sorting the two arrays first, then find the same elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int[] intersect_sort(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int len1 = nums1.length;
int len2 = nums2.length;
int[] ans = new int[Math.min(len1, len2)];
int idx = 0;
int p = 0;
int q = 0;
while (p < len1 && q < len2) {
if (nums1[p] == nums2[q]) {
ans[idx++] = nums1[p];
p++;
q++;
} else if (nums1[p] < nums2[q]) {
p++;
} else {
q++;
}
}

return Arrays.copyOfRange(ans, 0, idx);
}

Analysis

  • Time Complexity: O(mlogm+nlogn)O(mlogm+nlogn)
  • Space Complexity: O(min(m+n))O(min(m+n))

Solution 2 HashMap

Choose the array which is less and use HashMap to store the elements of the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int[] intersect_sort_hash(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return intersect_sort_hash(nums2, nums1);
}
int len1 = nums1.length;
int len2 = nums2.length;
Map<Integer, Integer> numFreq = new HashMap<>();
for (int i = 0; i < len1; i++) {
numFreq.put(nums1[i], numFreq.getOrDefault(nums1[i], 0) + 1);
}

int[] ans = new int[len1];
int idx = 0;
for (int i = 0; i < len2; i++) {
if (numFreq.containsKey(nums2[i])) {
ans[idx++] = nums2[i];
int freq = numFreq.get(nums2[i]);
if (freq > 1) {
numFreq.put(nums2[i], freq - 1);
} else {
numFreq.remove(nums2[i]);
}
}
}

return Arrays.copyOfRange(ans, 0, idx);
}

Analysis

  • Time Complexity: O(m+n)O(m+n).
  • Space Complexity: O(min(m+n))O(min(m+n)).

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗