Intersection of Two Arrays
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This straightforward approach involves using nested loops. We iterate through every element of the first array and, for each element, we iterate through the entire second array to check for a match. To ensure the final result contains only unique elements, we use a HashSet to store the common numbers we find.
Algorithm
- Initialize an empty
HashSetcalledresultSetto store the unique intersection elements. - Iterate through each element
num1in the first array,nums1. - For each
num1, start a nested loop to iterate through each elementnum2in the second array,nums2. - Inside the nested loop, compare
num1andnum2. - If
num1is equal tonum2, it means we've found a common element. Add this element to theresultSet. TheHashSetwill automatically handle duplicates. - After both loops have finished, the
resultSetcontains all unique common elements. - Create a new integer array with a size equal to the size of the
resultSet. - Iterate through the
resultSetand copy each element into the new array. - Return the final array.
Walkthrough
The brute-force method is the most intuitive way to solve the problem. We take each element from the first array, nums1, and compare it against every element in the second array, nums2. If a match is found, we add it to a separate data structure that stores our results.
To meet the requirement that each element in the result must be unique, a HashSet is an ideal choice for storing the intersection. A HashSet does not allow duplicate values, so if we find a common number multiple times, it will only be stored once.
After checking all pairs of elements, the HashSet will contain the complete, unique intersection of the two arrays. The final step is to convert this HashSet into an array before returning it.
import java.util.HashSet;import java.util.Set; 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); break; // Optimization: once found, move to the next num1 } } } // Convert the HashSet to an array int[] result = new int[resultSet.size()]; int i = 0; for (int num : resultSet) { result[i++] = num; } return result; }}Complexity
Time
O(n * m), where `n` is the length of `nums1` and `m` is the length of `nums2`. For each of the `n` elements in `nums1`, we iterate through all `m` elements of `nums2`.
Space
O(k), where k is the number of unique elements in the intersection. This space is used by the `HashSet` to store the result. In the worst case, k can be `min(nums1.length, nums2.length)`.
Trade-offs
Pros
Simple to understand and implement.
Requires minimal auxiliary data structures (only for the result).
Cons
Extremely inefficient for larger arrays, with a quadratic time complexity.
Likely to result in a 'Time Limit Exceeded' (TLE) error on most online judges for non-trivial input sizes.
Solutions
Solution
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var intersection = function (nums1, nums2) { const s = Array(1001).fill(false); for (const x of nums1) { s[x] = true; } const ans = []; for (const x of nums2) { if (s[x]) { ans.push(x); s[x] = false; } } return ans; };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.