LeetCode 2956 - Find Common Elements Between Two Arrays

LeetCode Problem 2956

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

Problem Understanding

This problem asks us to compare two integer arrays and count how many elements from one array appear in the other.

More specifically, we need to compute two values:

• answer1 is the number of indices i in nums1 such that nums1[i] appears at least once in nums2.
• answer2 is the number of indices i in nums2 such that nums2[i] appears at least once in nums1.

An important detail is that we are counting indices, not unique values. This means duplicates matter. If a value appears multiple times in one array and exists at least once in the other array, each occurrence contributes to the answer.

For example, if nums1 = [2,3,2] and nums2 = [1,2], both occurrences of 2 in nums1 count because 2 exists in nums2. Therefore, answer1 = 2.

The input consists of two integer arrays:

• nums1 of length n
• nums2 of length m

The output is a list of two integers:

[answer1, answer2]

The constraints are relatively small:

• 1 <= n, m <= 100
• 1 <= nums1[i], nums2[i] <= 100

These limits tell us that even a brute-force solution would be acceptable because the arrays are very small. However, we should still aim for a clean and efficient approach.

There are several important edge cases to consider. First, arrays may contain duplicates, which means we must count every qualifying index independently. Second, arrays may share no common values at all, resulting in [0,0]. Third, one array may consist entirely of repeated values that exist in the other array, meaning every index contributes to the count. The problem guarantees that both arrays contain at least one element, so we never need to handle empty inputs.

Approaches

Brute Force Approach

The simplest solution is to check every element in one array against every element in the other.

For answer1, we iterate through nums1 and search through nums2 to determine whether the current value exists. If we find a match, we increment the counter.

We repeat the same process in reverse for answer2, iterating through nums2 and checking whether each value exists in nums1.

This approach is correct because it explicitly verifies whether each element exists in the opposite array. Since the problem asks only for existence and not frequency matching, we can stop searching as soon as we find one match.

However, this approach is inefficient because every lookup may scan the entire opposite array. If n and m are the lengths of the arrays, the total time complexity becomes O(n × m).

Optimal Approach, Hash Set Lookup

The key observation is that we repeatedly ask the same question:

Does this number exist in the other array?

A hash set is ideal for membership testing because lookup operations are approximately O(1).

We can convert both arrays into sets:

• set1 = set(nums1)
• set2 = set(nums2)

Then:

• Count how many elements in nums1 appear in set2
• Count how many elements in nums2 appear in set1

This removes repeated scanning and makes membership checking very efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(1)	Check every element against the opposite array
Optimal	O(n + m)	O(n + m)	Use hash sets for constant time membership lookup

Algorithm Walkthrough

1. Convert nums1 into a hash set called set1.

This allows us to quickly determine whether any number exists in nums1 without repeatedly scanning the array. 2. Convert nums2 into a hash set called set2.

Similarly, this gives constant time membership checks for values from nums2. 3. Initialize a counter for answer1.

Iterate through nums1. For each number, check whether it exists in set2.

If it exists, increment answer1. 4. Initialize a counter for answer2.

Iterate through nums2. For each number, check whether it exists in set1.

If it exists, increment answer2. 5. Return the result as:

[answer1, answer2]

The reason we iterate over the original arrays instead of the sets is that duplicates must still count separately. Using only the sets would incorrectly ignore repeated values.

Why it works

The algorithm works because the hash sets preserve exactly the information we need, whether a value exists in the opposite array. Every element in nums1 is checked independently against set2, ensuring every qualifying index contributes to answer1, including duplicates. The same reasoning applies symmetrically for nums2 and answer2. Since membership in a set accurately answers the existence question, the algorithm always produces the correct result.

Python Solution

from typing import List

class Solution:
    def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)

        answer1 = 0
        for num in nums1:
            if num in set2:
                answer1 += 1

        answer2 = 0
        for num in nums2:
            if num in set1:
                answer2 += 1

        return [answer1, answer2]

The implementation begins by converting both arrays into sets. This preprocessing step is important because it allows constant time membership checks.

Next, the code iterates through nums1. Each number is checked against set2. If the number exists, the counter increases. Notice that we iterate over the original array, not the set, because duplicate elements must count separately.

The same process is repeated for nums2, checking membership in set1.

Finally, the method returns both counts in the required format.

Go Solution

func findIntersectionValues(nums1 []int, nums2 []int) []int {
	set1 := make(map[int]bool)
	set2 := make(map[int]bool)

	for _, num := range nums1 {
		set1[num] = true
	}

	for _, num := range nums2 {
		set2[num] = true
	}

	answer1 := 0
	for _, num := range nums1 {
		if set2[num] {
			answer1++
		}
	}

	answer2 := 0
	for _, num := range nums2 {
		if set1[num] {
			answer2++
		}
	}

	return []int{answer1, answer2}
}

The Go implementation follows the same algorithm but uses map[int]bool to simulate a hash set because Go does not have a built in set type.

Unlike Python, Go requires explicit map initialization with make. Membership checking is straightforward because reading a missing key from a boolean map returns false.

There are no integer overflow concerns here because the maximum count is at most 100, well within Go's integer limits. Empty arrays are also not an issue since the problem guarantees at least one element in each array.

Worked Examples

Example 1

Input:

nums1 = [2,3,2]
nums2 = [1,2]

First, construct the sets:

set1 = {2,3}
set2 = {1,2}

Counting answer1

Index	Value in nums1	Exists in set2?	answer1
0	2	Yes	1
1	3	No	1
2	2	Yes	2

Final:

answer1 = 2

Counting answer2

Index	Value in nums2	Exists in set1?	answer2
0	1	No	0
1	2	Yes	1

Final result:

[2,1]

Example 2

Input:

nums1 = [4,3,2,3,1]
nums2 = [2,2,5,2,3,6]

Construct sets:

set1 = {1,2,3,4}
set2 = {2,3,5,6}

Counting answer1

Index	Value	Exists in set2?	answer1
0	4	No	0
1	3	Yes	1
2	2	Yes	2
3	3	Yes	3
4	1	No	3

Counting answer2

Index	Value	Exists in set1?	answer2
0	2	Yes	1
1	2	Yes	2
2	5	No	2
3	2	Yes	3
4	3	Yes	4
5	6	No	4

Final result:

[3,4]

Example 3

Input:

nums1 = [3,4,2,3]
nums2 = [1,5]

Construct sets:

set1 = {2,3,4}
set2 = {1,5}

Counting answer1

Index	Value	Exists in set2?	answer1
0	3	No	0
1	4	No	0
2	2	No	0
3	3	No	0

Counting answer2

Index	Value	Exists in set1?	answer2
0	1	No	0
1	5	No	0

Final result:

[0,0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Building the sets takes linear time, and each array is scanned once
Space	O(n + m)	The two hash sets store unique elements from both arrays

The time complexity is linear because each array is traversed a constant number of times. Creating the sets costs O(n + m), and counting valid indices also costs O(n + m).

The space complexity is O(n + m) because, in the worst case, every element is unique and stored in the hash sets.

Test Cases

solution = Solution()

# Provided examples
assert solution.findIntersectionValues([2, 3, 2], [1, 2]) == [2, 1]  # example 1
assert solution.findIntersectionValues([4, 3, 2, 3, 1], [2, 2, 5, 2, 3, 6]) == [3, 4]  # example 2
assert solution.findIntersectionValues([3, 4, 2, 3], [1, 5]) == [0, 0]  # example 3

# Single element arrays
assert solution.findIntersectionValues([1], [1]) == [1, 1]  # same value
assert solution.findIntersectionValues([1], [2]) == [0, 0]  # no overlap

# Duplicate values
assert solution.findIntersectionValues([2, 2, 2], [2]) == [3, 1]  # duplicates count separately
assert solution.findIntersectionValues([1], [1, 1, 1]) == [1, 3]  # repeated matches

# No common elements
assert solution.findIntersectionValues([1, 2, 3], [4, 5, 6]) == [0, 0]  # disjoint arrays

# All elements common
assert solution.findIntersectionValues([1, 2, 3], [3, 2, 1]) == [3, 3]  # all shared

# Boundary values
assert solution.findIntersectionValues([100], [100]) == [1, 1]  # max value constraint
assert solution.findIntersectionValues([1] * 100, [1]) == [100, 1]  # max repeated elements

Test	Why
[2,3,2], [1,2]	Validates duplicate counting
[4,3,2,3,1], [2,2,5,2,3,6]	Validates mixed overlap and duplicates
[3,4,2,3], [1,5]	Validates no overlap
[1], [1]	Smallest valid matching input
[1], [2]	Smallest valid non matching input
[2,2,2], [2]	Ensures duplicates count independently
[1], [1,1,1]	Validates duplicate handling in second array
[1,2,3], [4,5,6]	Tests completely disjoint arrays
[1,2,3], [3,2,1]	Tests full overlap
[100], [100]	Verifies upper numeric bound
[1] * 100, [1]	Stresses maximum array size behavior

Edge Cases

Arrays with duplicates

A common mistake is counting only unique values instead of counting indices. For example, with nums1 = [2,2,2] and nums2 = [2], the correct result is [3,1], not [1,1]. Every occurrence of 2 in nums1 counts because the problem asks about indices. The implementation handles this correctly by iterating over the original arrays rather than the sets.

No overlapping elements

If the arrays share no common values, the result should be [0,0]. A naive implementation might accidentally increment counts incorrectly or assume some overlap exists. Since our solution uses explicit membership checks, elements that do not exist in the opposite set simply do not contribute to the answer.

One array contains repeated values and the other contains one match

Consider nums1 = [5,5,5,5] and nums2 = [5]. The answer should be [4,1]. This case can expose bugs in implementations that only compare unique values. Because our algorithm checks every element in the original arrays, repeated values are counted correctly.

Minimum sized arrays

The smallest possible inputs are arrays of length 1. For example, [1] and [2] should return [0,0], while [1] and [1] should return [1,1]. The implementation naturally handles these cases because the loops still execute correctly even for a single element.