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.
This approach uses a straightforward, nested-loop method to solve the problem. For each element in the first array, we iterate through the entire second array to check for its existence. We repeat this process for the second array against the first.
Algorithm
- Initialize
answer1andanswer2to 0. - To calculate
answer1, iterate through each elementnum1innums1. - For each
num1, start a nested loop to iterate through each elementnum2innums2. - If
num1is equal tonum2, it meansnum1exists innums2. Incrementanswer1and break the inner loop to avoid multiple counts for the samenum1and move to the next element innums1. - To calculate
answer2, repeat the process. Iterate through each elementnum2innums2. - For each
num2, start a nested loop to iterate through each elementnum1innums1. - If
num2is equal tonum1, incrementanswer2and break the inner loop. - Finally, return the result as
[answer1, answer2].
Walkthrough
To find answer1, we iterate through each element of nums1. For each of these elements, we perform another loop through all elements of nums2. If a match is found, we increment answer1 and break the inner loop to proceed to the next element in nums1.
Similarly, to find answer2, we iterate through each element of nums2. For each element, we loop through nums1 to find a match. If a match is found, we increment answer2 and break the inner loop.
This method is simple to understand and implement but is not efficient for large arrays.
class Solution { public int[] findIntersectionValues(int[] nums1, int[] nums2) { int answer1 = 0; int answer2 = 0; // Helper function to check if a value exists in an array // This could be inlined as well for (int num1 : nums1) { for (int num2 : nums2) { if (num1 == num2) { answer1++; break; // Found a match, move to the next element in nums1 } } } for (int num2 : nums2) { for (int num1 : nums1) { if (num2 == num1) { answer2++; break; // Found a match, move to the next element in nums2 } } } return new int[]{answer1, answer2}; }}Complexity
Time
O(n * m), where `n` is the length of `nums1` and `m` is the length of `nums2`. We have two separate sets of nested loops, one taking O(n * m) and the other O(m * n), resulting in a total time complexity of O(n * m).
Space
O(1), as we only use a few variables to store the counts and loop indices. The space for the output array is not considered.
Trade-offs
Pros
Simple to implement and understand.
Requires minimal extra space (O(1)).
Cons
Highly inefficient with a quadratic time complexity, which will be very slow for large arrays.
Likely to result in a 'Time Limit Exceeded' (TLE) error on platforms with stricter time limits for larger inputs.
Given the constraint that all numbers are between 1 and 100, we can use a highly efficient, constant-space optimization. Instead of a general-purpose hash set, we can use a simple boolean array as a direct-address table to track the presence of numbers.
Algorithm
- Create a boolean array
presentInNums1of size 101, initialized tofalse. - Iterate through
nums1, and for eachnum, setpresentInNums1[num] = true. - Create a boolean array
presentInNums2of size 101, initialized tofalse. - Iterate through
nums2, and for eachnum, setpresentInNums2[num] = true. - Initialize
answer1to 0. Iterate throughnums1, and for eachnum, ifpresentInNums2[num]istrue, incrementanswer1. - Initialize
answer2to 0. Iterate throughnums2, and for eachnum, ifpresentInNums1[num]istrue, incrementanswer2. - Return the array
[answer1, answer2].
Walkthrough
We create two boolean arrays, presentInNums1 and presentInNums2, both of size 101 (to cover indices 1 to 100). These arrays will act as our lookup tables.
We iterate through nums1 and mark the corresponding indices in presentInNums1 as true. For example, if we see the number 5, we set presentInNums1[5] = true.
We do the same for nums2 and presentInNums2.
To find answer1, we iterate through nums1 again. For each number num, we check presentInNums2[num]. If it's true, we increment answer1.
To find answer2, we iterate through nums2. For each number num, we check presentInNums1[num]. If it's true, we increment answer2.
This approach has the same time complexity as the hash set method but uses constant extra space, making it the most efficient solution for the given constraints.
class Solution { public int[] findIntersectionValues(int[] nums1, int[] nums2) { boolean[] presentInNums1 = new boolean[101]; for (int num : nums1) { presentInNums1[num] = true; } boolean[] presentInNums2 = new boolean[101]; for (int num : nums2) { presentInNums2[num] = true; } int answer1 = 0; for (int num : nums1) { if (presentInNums2[num]) { answer1++; } } int answer2 = 0; for (int num : nums2) { if (presentInNums1[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`. The process involves four separate linear passes: two to populate the boolean arrays and two to count the common elements.
Space
O(1), because the size of the boolean arrays (101) is constant and does not depend on the input array sizes `n` and `m`.
Trade-offs
Pros
Optimal time complexity of O(n + m).
Constant space complexity, making it very memory-efficient.
Often faster in practice than hash sets due to better cache performance and no hashing overhead.
Cons
This approach is only applicable because of the specific constraint on the range of values in the input arrays (1 to 100). It would not be feasible for a large or unbounded range of numbers.
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; }}class Solution {public: vector<int> findIntersectionValues(vector<int> &nums1, vector<int> &nums2) { int s1[101]{}; int s2[101]{}; for (int &x : nums1) { s1[x] = 1; } for (int &x : nums2) { s2[x] = 1; } vector<int> ans(2); for (int &x : nums1) { ans[0] += s2[x]; } for (int &x : nums2) { ans[1] += s1[x]; } return ans; }};class Solution: def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]: s1, s2 = set(nums1), set(nums2) return [sum(x in s2 for x in nums1), sum(x in s1 for x in nums2)]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.