Find Common Elements Between Two Arrays
EasyPrompt
You are given two integer arrays nums1 and nums2 of sizes n and m, respectively. Calculate the following values:
answer1: the number of indicesisuch thatnums1[i]exists innums2.answer2: the number of indicesisuch thatnums2[i]exists innums1.
Return [answer1,answer2].
Example 1:
Input: nums1 = [2,3,2], nums2 = [1,2]
Output: [2,1]
Explanation:
Example 2:
Input: nums1 = [4,3,2,3,1], nums2 = [2,2,5,2,3,6]
Output: [3,4]
Explanation:
The elements at indices 1, 2, and 3 in nums1 exist in nums2 as well. So answer1 is 3.
The elements at indices 0, 1, 3, and 4 in nums2 exist in nums1. So answer2 is 4.
Example 3:
Input: nums1 = [3,4,2,3], nums2 = [1,5]
Output: [0,0]
Explanation:
No numbers are common between nums1 and nums2, so answer is [0,0].
Constraints:
n == nums1.lengthm == nums2.length1 <= n, m <= 1001 <= nums1[i], nums2[i] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
To improve the time complexity, we can use hash sets. A hash set provides average O(1) time complexity for checking the existence of an element. We can convert the arrays into hash sets to speed up the search process significantly.
Algorithm
- Create a
HashSetnamedset1and add all elements fromnums1to it. - Create another
HashSetnamedset2and add all elements fromnums2to it. - Initialize
answer1to 0. - Iterate through each element
numin the originalnums1array. Ifset2containsnum, incrementanswer1. - Initialize
answer2to 0. - Iterate through each element
numin the originalnums2array. Ifset1containsnum, incrementanswer2. - Return the array
[answer1, answer2].
Walkthrough
First, we create two hash sets, set1 and set2, and populate them with the unique elements from nums1 and nums2, respectively. This step takes O(n + m) time.
Then, to calculate answer1, we iterate through the original nums1 array. For each element, we check if it exists in set2. Since lookups in a hash set are O(1) on average, this loop takes O(n) time.
Similarly, to calculate answer2, we iterate through the original nums2 array and check for each element's presence in set1. This loop takes O(m) time.
The total time complexity is dominated by the linear scans, making it much faster than the brute-force approach.
import java.util.HashSet;import java.util.Set; class Solution { public int[] findIntersectionValues(int[] nums1, int[] nums2) { Set<Integer> set1 = new HashSet<>(); for (int num : nums1) { set1.add(num); } Set<Integer> set2 = new HashSet<>(); for (int num : nums2) { set2.add(num); } int answer1 = 0; for (int num : nums1) { if (set2.contains(num)) { answer1++; } } int answer2 = 0; for (int num : nums2) { if (set1.contains(num)) { answer2++; } } return new int[]{answer1, answer2}; }}Complexity
Time
O(n + m), where `n` is the length of `nums1` and `m` is the length of `nums2`. Populating the sets takes O(n + m), and the two counting loops take O(n) and O(m) respectively.
Space
O(n + m), as we need to store the unique elements of both arrays in two separate hash sets. In the worst case, where all elements are unique, the space is proportional to the sum of the lengths of the arrays.
Trade-offs
Pros
Significantly faster than the brute-force approach with a linear time complexity.
A general-purpose solution that works well even if the range of numbers is large or not constrained.
Cons
Uses extra space proportional to the number of unique elements in the arrays.
Solutions
Solution
class Solution {public int[] findIntersectionValues(int[] nums1, int[] nums2) { int[] s1 = new int[101]; int[] s2 = new int[101]; for (int x : nums1) { s1[x] = 1; } for (int x : nums2) { s2[x] = 1; } int[] ans = new int[2]; for (int x : nums1) { ans[0] += s2[x]; } for (int x : nums2) { ans[1] += s1[x]; } 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.