2956. Find Common Elements Between Two Arrays
SourceBiweekly Contest 119 Q1DifficultyEasyRating1214
Description
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:
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
Solutions
Solution 1: Hash Table or Array
Thinking
Count how many values of \(\textit{nums1}\) occur in \(\textit{nums2}\) and the opposite; this is membership, not index alignment. \(n,m \le 100\), so build two sets and scan each array once.
The domain is at most \(100\), so a boolean array would also work. Return the pair.
We can use two hash tables or arrays \(\textit{s1}\) and \(\textit{s2}\) to record the elements that appear in the two arrays respectively.
Next, we create an array \(\textit{ans}\) of length \(2\), where \(\textit{ans}[0]\) represents the number of elements in \(\textit{nums1}\) that appear in \(\textit{s2}\), and \(\textit{ans}[1]\) represents the number of elements in \(\textit{nums2}\) that appear in \(\textit{s1}\).
Then, we traverse each element \(x\) in the array \(\textit{nums1}\). If \(x\) has appeared in \(\textit{s2}\), we increment \(\textit{ans}[0]\). After that, we traverse each element \(x\) in the array \(\textit{nums2}\). If \(x\) has appeared in \(\textit{s1}\), we increment \(\textit{ans}[1]\).
Finally, we return the array \(\textit{ans}\).
The time complexity is \(O(n + m)\), and the space complexity is \(O(n + m)\), where \(n\) and \(m\) are the lengths of the arrays \(\textit{nums1}\) and \(\textit{nums2}\) respectively.
1 2 3 4 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |
