Difficulty: Easy | Acceptance: 84.50% | Paid: No Topics: Array, Hash Table
You are given two 0-indexed integer arrays nums1 and nums2 of sizes n and m, respectively.
Return the answer array ans of size 2 such that:
ans[0] is the number of indices i (0-indexed) such that nums1[i] exists in nums2. ans[1] is the number of indices i (0-indexed) such that nums2[i] exists in nums1.
- Examples
- Constraints
- Brute Force
- Hash Set
- Hash Map
Examples
Example 1
Input:
nums1 = [2,3,2], nums2 = [1,2]
Output:
[2,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.length
m == nums2.length
1 <= n, m <= 100
1 <= nums1[i], nums2[i] <= 100
Brute Force
Intuition For each element in nums1, check if it exists in nums2. For each element in nums2, check if it exists in nums1.
Steps
- Initialize two counters to 0.
- For each element in nums1, check if it exists in nums2 and increment the first counter.
- For each element in nums2, check if it exists in nums1 and increment the second counter.
- Return the two counters as an array.
from typing import List
class Solution:
def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]:
count1 = 0
count2 = 0
for num in nums1:
if num in nums2:
count1 += 1
for num in nums2:
if num in nums1:
count2 += 1
return [count1, count2]
Complexity
- Time: O(n × m) where n is the length of nums1 and m is the length of nums2
- Space: O(1)
- Notes: Simple but inefficient for large arrays
Hash Set
Intuition Convert both arrays to sets for O(1) lookup, then count how many elements in each array exist in the other set.
Steps
- Convert nums1 and nums2 to sets.
- Count elements in nums1 that exist in set2.
- Count elements in nums2 that exist in set1.
- Return the two counts as an array.
from typing import List
class Solution:
def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]:
set1 = set(nums1)
set2 = set(nums2)
count1 = sum(1 for num in nums1 if num in set2)
count2 = sum(1 for num in nums2 if num in set1)
return [count1, count2]
Complexity
- Time: O(n + m) where n is the length of nums1 and m is the length of nums2
- Space: O(n + m) for the two sets
- Notes: Optimal time complexity with reasonable space trade-off
Hash Map
Intuition Use hash maps to count frequencies of elements in both arrays, then check for common elements.
Steps
- Create frequency maps for both arrays.
- Iterate through nums1 and count elements that exist in nums2’s frequency map.
- Iterate through nums2 and count elements that exist in nums1’s frequency map.
- Return the two counts as an array.
from typing import List
from collections import Counter
class Solution:
def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]:
count1 = Counter(nums1)
count2 = Counter(nums2)
result1 = 0
for num in nums1:
if num in count2:
result1 += 1
result2 = 0
for num in nums2:
if num in count1:
result2 += 1
return [result1, result2]
Complexity
- Time: O(n + m) where n is the length of nums1 and m is the length of nums2
- Space: O(n + m) for the two maps
- Notes: Similar to Hash Set approach but with frequency information (not needed for this problem)