Leetcode 2956. Find Common Elements Between Two Arrays

Problem

You are given two integer arrays. Your task is to determine how many elements from each array appear in the other array.

Specifically, return an array of two integers where:

• The first integer represents the count of indices in the first array whose values exist somewhere in the second array
• The second integer represents the count of indices in the second array whose values exist somewhere in the first array

Important: Each index is counted independently. If the same value appears multiple times in an array, each occurrence counts separately toward the total.

Requirements

1. Return an array containing exactly two integers: [count1, count2]
2. count1 represents how many positions in arr1 contain values that appear anywhere in arr2
3. count2 represents how many positions in arr2 contain values that appear anywhere in arr1
4. Duplicate values should be counted each time they appear

Constraints

• 1 ≤ arr1.length, arr2.length ≤ 1000
• 1 ≤ arr1[i], arr2[i] ≤ 100
• Optimize for time efficiency using appropriate data structures

Examples

Example 1:

` Input: arr1 = [2, 3, 2], arr2 = [1, 2] Output: [2, 1] Explanation:

• In arr1: index 0 has value 2 (exists in arr2), index 1 has value 3 (doesn't exist in arr2), index 2 has value 2 (exists in arr2). Total: 2
• In arr2: index 0 has value 1 (doesn't exist in arr1), index 1 has value 2 (exists in arr1). Total: 1 `

Example 2:

Input: arr1 = [1, 2, 3], arr2 = [4, 5, 6] Output: [0, 0] Explanation: There are no common values between the two arrays, so both counts are 0.

Example 3:

` Input: arr1 = [4, 3, 2, 3, 1], arr2 = [2, 2, 5, 2, 3, 6] Output: [3, 4] Explanation:

• In arr1: values 3 (index 1), 2 (index 2), and 3 (index 3) appear in arr2. Total: 3
• In arr2: values 2 (indices 0, 1, 3) and 3 (index 4) appear in arr1. Total: 4 `

Hint 1: Efficient Lookup To efficiently check if a value exists in an array, convert one or both arrays into a data structure that allows fast membership testing. What data structure provides O(1) average-case lookup time?

Hint 2: Independent Counting You need to iterate through each array and count how many elements from that array exist in the other. Convert both arrays to sets first to avoid repeated lookups, then iterate through each original array counting matches.

Full Solution ` def countCommonElements(arr1, arr2): # Convert both arrays to sets for O(1) membership checking set1 = set(arr1) set2 = set(arr2)

# Count elements in arr1 that exist in arr2
count1 = 0
for num in arr1:
    if num in set2:
        count1 += 1

# Count elements in arr2 that exist in arr1
count2 = 0
for num in arr2:
    if num in set1:
        count2 += 1

return [count1, count2]

`

Approach:

The solution uses sets to enable efficient membership checking. Here's the strategy:

1. Create Sets: Convert both input arrays to sets. This allows us to check if a value exists in constant time on average, rather than linear time with array searches.
2. Count Matches in First Array: Iterate through each element in arr1. For each element, check if it exists in set2 (derived from arr2). Increment count1 for each match.
3. Count Matches in Second Array: Similarly, iterate through each element in arr2 and check if it exists in set1 (derived from arr1). Increment count2 for each match.
4. Return Results: Return both counts as an array.

Why This Works:

By using sets for membership testing, we avoid nested loops that would result in O(n × m) time complexity. Each element is checked against a set in O(1) average time.

Complexity Analysis:

• Time Complexity: O(n + m) where n is the length of arr1 and m is the length of arr2. We iterate through each array once, and set operations (creation and lookup) are O(1) on average.
• Space Complexity: O(n + m) to store the two sets containing unique elements from both arrays.