The Intersection of Two Arrays problem asks you to find the unique elements that appear in both arrays. Imagine two groups of people; this task is like finding out who belongs to both groups. The challenge is to do this efficiently, especially when the arrays are large. The goal is to return the intersection of the two arrays as a list of unique elements.
Brute Force Approach
The brute force approach compares every element in one array to every element in the other. If a match is found, it’s added to the result set.
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> resultSet = new HashSet<>();
for (int num1 : nums1) {
for (int num2 : nums2) {
if (num1 == num2) {
resultSet.add(num1);
}
}
}
// Convert the result set to an array
int[] result = new int[resultSet.size()];
int index = 0;
for (int num : resultSet) {
result[index++] = num;
}
return result;
}
}• The code iterates through every combination of elements in nums1 and nums2 to check for matches.
• It uses a Set to ensure that only unique elements are added to the result.
• Drawback: The time complexity is O(n \times m), where n and m are the sizes of the two arrays. This is inefficient for large inputs.
Optimized Approach: Using HashSet
The optimized approach uses a HashSet to store elements from one array and checks for matches in the other array. This leverages the O(1) average-time complexity of set operations.
• Algorithm: Hash-based lookup.
• Pattern: Set Intersection. This pattern is efficient for problems involving comparisons between two collections.
The key observation is that we need to know quickly if an element from one array exists in the other. A HashSet provides O(1) average-time complexity for lookups, making it ideal for this task. By iterating through one array and using the set to check membership, we avoid the nested loops of the brute force approach.
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
// Store all elements of nums1 in a HashSet
Set<Integer> set1 = new HashSet<>();
for (int num : nums1) {
set1.add(num);
}
// Store the intersection in another HashSet
Set<Integer> resultSet = new HashSet<>();
for (int num : nums2) {
if (set1.contains(num)) {
resultSet.add(num);
}
}
// Convert the result set to an array
int[] result = new int[resultSet.size()];
int index = 0;
for (int num : resultSet) {
result[index++] = num;
}
return result;
}
}1. Create a HashSet and add all elements of nums1 to it.
2. Create another HashSet for storing the intersection results.
3. Iterate through nums2:
• If an element exists in the first set, add it to the result set.
4. Convert the result set to an array and return it.
Why This Problem is Valuable To Learn
The Intersection of Two Arrays problem is excellent for understanding how data structures like HashSet can optimize problems involving comparisons and uniqueness. It teaches critical patterns like set operations, hashing, and efficient search strategies, which are widely applicable in real-world scenarios and advanced coding challenges.
