Problem 39 - Intersection of Two Arrays
Explore our archive for previous posts.
Question
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
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]
Explanation: [4,9] is also accepted.Constraints:
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
Approach
The core idea behind this approach is to use HashSet data structures. We use two HashSet collections, one for each input array, to store unique elements. By adding elements from each array into their respective HashSet, we ensure that duplicates are automatically eliminated. After creating these sets, we perform a simple operation to identify common elements. If an element exists in both sets, it means it's a common element of the two arrays. We store these common elements into a final ArrayList and return the result.
Solution
Solve it here
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
// Create two sets to store unique elements from both arrays
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
// Add elements from the first array to set1
for (int num : nums1) {
set1.add(num);
}
// Add elements from the second array to set2
for (int num : nums2) {
set2.add(num);
}
// Create a list to store the intersection of elements
List<Integer> result = new ArrayList<>();
// Iterate through set1 and check for common elements in set2
for (int num : set1) {
if (set2.contains(num)) {
result.add(num);
}
}
// Convert the ArrayList to an integer array
int[] intersection = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
intersection[i] = result.get(i);
}
return intersection;
}
}Time and space complexity
Time Complexity: The time complexity of this solution is O(m + n), where m and n are the lengths of nums1 and nums2, respectively. This is because we iterate through both arrays once.
Space Complexity: The space complexity is O(m + n) as well since we use two sets to store unique elements from both input arrays.
Explore more?
Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!
