LeetCode Problem 349
Link of the Problem to try -: Link
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
Solution: Using HashMap and HashSet for Intersection
Core Objective: The primary goal of this problem is to identify common elements between two arrays and return them as a unique set. To achieve this efficiently, we utilize a combination of a HashMap for quick lookup and a HashSet to handle uniqueness in the result.
Logic & Implementation:
- Populate Lookup Table: We begin by iterating through the first array (
nums1) and storing its elements in a HashMap. This allows us to verify the existence of any number in $O(1)$ average time. - Identify Intersection: Next, we iterate through the second array (
nums2). For each element, we check if it exists within our HashMap. - Handle Uniqueness: If a match is found, we add the element to a HashSet. This is a crucial step because the problem requires the output to contain unique elements, even if a common number appears multiple times in the input arrays.
- Final Conversion: Since the required return type is an array, we determine the size of our HashSet to initialize the result array. Using a for-each loop, we transfer the values from the Set into the array and return it as the final answer.
Code Implementation:
public int[] intersection(int[] nums1, int[] nums2) {
// HashMap to store elements from the first array for lookup
HashMap<Integer, Integer> mp = new HashMap<>();
// HashSet to store unique common elements
HashSet<Integer> ms = new HashSet<>();
// Populate the map with elements from nums1
for (int i = 0; i < nums1.length; i++) {
if (mp.containsKey(nums1[i])) {
continue;
}
mp.put(nums1[i], i);
}
// Check for common elements in nums2
for (int i = 0; i < nums2.length; i++) {
if (mp.containsKey(nums2[i])) {
ms.add(nums2[i]); // HashSet ensures duplicates are not added
}
}
// Convert the HashSet to the final integer array
int[] ans = new int[ms.size()];
int co = 0;
for (int i : ms) {
ans[co] = i;
co++;
}
return ans;
}
