
Problem Statement
In this problem, you are provided with two integer arrays, nums1
and nums2
. Your task is to find out the elements that are present in both arrays, ensuring that each element in the resultant array is unique. This result does not require any specific order, meaning that as long as all the unique common elements are included, the sequence in which they appear does not matter.
Examples
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 <= 1000
0 <= nums1[i], nums2[i] <= 1000
Approach and Intuition
The problem of finding the intersection of two sets is quite common in data processing. The goal is to determine which items are shared between nums1
and nums2
while ignoring duplicates within the intersection.
- First, convert both
nums1
andnums2
into sets. This transformation automatically removes duplicates from each list and permits operations that are optimal for set interactions. - Then, use the intersection method available for sets. This method efficiently finds common elements between the two sets.
- The resultant set from the intersection operation can then be converted back into a list to satisfy the requirement of returning an array.
- The function signature involves simply returning this resultant list as the solution.
This approach is efficient due to the properties of sets in Python, which offer average-time complexity for insertion, deletion, and membership tests. Thus, the operations of converting lists to sets and finding their intersection are performed swiftly, which is ideal given the problem constraints.
Solutions
- Java
class Solution {
public int[] findIntersection(int[] array1, int[] array2) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> tempResult = new ArrayList<>();
for (int num : array1) {
map.put(num, 1);
}
for (int num : array2) {
if (map.containsKey(num) && map.get(num) == 1) {
tempResult.add(num);
map.put(num, 0);
}
}
return tempResult.stream().mapToInt(i -> i).toArray();
}
}
The provided Java solution tackles the problem of finding the intersection of two arrays. In this implementation, two arrays are given as input (array1
and array2
), and the objective is to return a new array representing the common elements between them. Each element in the resulting intersection array must appear only once, even if it appears multiple times in the original arrays.
Here's a breakdown of how the code achieves this goal:
- Initialize a
HashMap
namedmap
to keep track of elements from the first array (array1
). - Populate this
map
using elements fromarray1
as keys, initially marking each with a count of1
to indicate their presence. - Create an
ArrayList
namedtempResult
to temporarily store the intersection elements. - Iterate over the second array (
array2
). For each element:- Check if the element is in
map
and has a marker of1
. - If so, add the element to
tempResult
and update the element's marker inmap
to0
to prevent duplication in case of further matches inarray2
.
- Check if the element is in
- Convert
tempResult
into an array of integers to match the function's return type using Java's stream API.
This approach ensures that the complexity is proportional to the size of array1
and array2
, achieving efficient mapping and retrieval operations. By marking array elements dynamically in the hashmap, this code efficiently filters out duplicates and ensures only intersection results are considered.
Make sure to consider edge cases, such as either of the arrays being empty, which would simply return an empty intersection, as the code handles such situations by default due to natural flow and checks.
No comments yet.