#2956

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find Common Elements Between Two Arrays

Quickly find all numbers that appear in both arrays using scanning and hash lookup to handle duplicates efficiently.

Problem Statement

You are given two integer arrays, nums1 and nums2, containing n and m elements respectively. Your task is to determine all elements that exist in both arrays and count how many are common in each direction.

Return an array [countInNums1, countInNums2], where countInNums1 is the number of elements in nums1 that appear in nums2, and countInNums2 is the number of elements in nums2 that appear in nums1. Consider duplicates separately for counting.

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]

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]

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

Solution Approach

Hash Set for Fast Lookup

Store all elements of nums2 in a hash set, then iterate over nums1 counting elements that exist in the set. This ensures O(1) lookup per element and simplifies handling duplicates.

Bidirectional Counting

After counting from nums1 to nums2, repeat the process swapping roles: put nums1 in a hash set and scan nums2 to get countInNums2. This ensures both directions are captured accurately.

Optional Brute Force for Small Inputs

Since constraints are small (arrays up to length 100), a nested loop comparing every element is feasible, but hash set scanning reduces redundant checks and scales better if constraints increase.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m) using hash sets for both arrays. Space complexity is O(n + m) for storing hash sets. Brute force is O(n*m) time and O(1) space, only suitable for small arrays.

What Interviewers Usually Probe

Check if the candidate considers both directions of counting elements.
Notice if duplicates are counted separately or ignored.
Evaluate if the candidate uses hash sets for faster lookup instead of nested loops.

Common Pitfalls or Variants

Common pitfalls

Counting duplicates incorrectly or only once instead of per occurrence.
Ignoring one direction of counting, giving an incomplete answer.
Using nested loops on larger inputs, leading to inefficient O(n*m) performance.

Follow-up variants

Return the actual common elements list instead of counts, preserving order from one array.
Handle more than two arrays, finding elements common to all arrays.
Compute intersection using sorted arrays and two-pointer technique instead of hash sets.

FAQ

What pattern does this problem follow?

It follows the array scanning plus hash lookup pattern, ideal for counting common elements efficiently.

Can I use brute force to solve this?

Yes, for small arrays up to 100 elements, brute force is feasible but less efficient than hash set scanning.

Do I need to count duplicates separately?

Yes, each occurrence should be counted separately to get accurate counts for both arrays.

What is the time complexity using hash sets?

Time complexity is O(n + m) because each element is checked once with O(1) lookup in the hash set.

What should I return if no elements are common?

Return [0,0], indicating zero common elements in both directions.

terminal

Solution

Solution 1: Hash Table or Array

We can use two hash tables or arrays $s1$ and $s2$ to record the elements that appear in the two arrays respectively.

1

2

3

4

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)]

Continue Practicing

#2958 length of longest subarray with at most k frequency #2963 count the number of good partitions #2965 find missing and repeated values