349. Intersection of Two Arrays
Tags: ‘Hash Table’, ‘Two Pointers’, ‘Binary Search’, ‘Sort’
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4]
Note:
- Each element in the result must be unique.
- The result can be in any order.
Solution
Refer to 1213 Intersection of Three Sorted Arrays
Naive solution using map, extra space required O(N1 + N2) O(N1)
public int[] intersection(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>(); // map occurance in nums2
List<Integer> list = new ArrayList<>();
for (int i: nums1) {
map.put(i, 0);
}
for (int i: nums2) {
if (map.containsKey(i) && map.get(i) == 0) {
list.add(i);
map.put(i, 1);
}
}
int[] result = new int[list.size()];
int i = 0;
for (Integer x: list) {
result[i] = x;
i++;
}
return result;
}
Two pointers and sorting O(nlogn) O(1)
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0;
int j = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
set.add(nums1[i]);
i++;
j++;
}
}
int[] result = new int[set.size()];
int k = 0;
for (Integer num : set) {
result[k++] = num;
}
return result;
}