Skip to main content
Talentd

Find Common Elements Between Two Arrays - Solution & Explanation

EasyArrayHash Table15 min readAsked at: Amazon, Meta, Google +2
Practice this problem

Problem Statement

You are given two integer arrays nums1 and nums2 of sizes n and m, respectively. Calculate the following values:

  • answer1 : the number of indices i such that nums1[i] exists in nums2.
  • answer2 : the number of indices i such that nums2[i] exists in nums1.

Return [answer1,answer2].

 

Example 1:

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

Output: [2,1]

Explanation:

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

Approach Overview

Problem Overview: You get two integer arrays, nums1 and nums2. For each array, count how many elements also appear in the other array. The result is a two‑element array where the first value counts matches from nums1 in nums2, and the second counts matches from nums2 in nums1.

Approach 1: Using Brute Force with Optimizations (O(n * m) time, O(1) space)

The straightforward method checks every element of one array against the other. For each value in nums1, iterate through nums2 and stop once a match is found. Repeat the same process in the opposite direction. Early termination slightly reduces unnecessary comparisons, but the worst‑case still requires scanning the full second array for each element. This approach relies only on nested iteration and basic comparisons, making it easy to implement but inefficient for larger inputs. It’s mainly useful for understanding the baseline before introducing better lookup structures.

Approach 2: Using Set for Efficient Look-Up (O(n + m) time, O(n + m) space)

A more efficient solution uses a set (hash table) for constant‑time membership checks. Convert nums1 and nums2 into sets, then iterate through each original array. For every value in nums1, check if it exists in the set built from nums2. Do the reverse for nums2. Hash lookups run in average O(1), so each array is scanned only once. This reduces the total complexity to O(n + m) while using extra memory for the sets. This pattern appears frequently in array problems that require fast membership checks and is a common use case for a hash table.

Recommended for interviews: The hash set approach is the expected solution. It demonstrates that you recognize when repeated membership checks can be optimized with a set. Showing the brute force approach first confirms you understand the baseline complexity, while moving to the O(n + m) hash‑based solution shows strong problem‑solving skills with hash table techniques.

Approach 1: Approach 1: Using Set for Efficient Look-Up

This approach leverages the efficient look-up capabilities of sets to find common elements between the arrays. By converting the second array into a set, we can quickly check for the existence of each element in the first array.

The function find_common_elements first converts nums2 into a set set_nums2 to utilize the average O(1) time complexity for look-up operations in Python sets. Then, it counts elements in nums1 that exist in set_nums2. Similarly, we convert nums1 to a set to find and count elements in nums2 that exist in the set.

Code

PythonJavaScriptJavaC#C++C

Python

JavaScript

Java

C#

C++

C

Complexity

Time Complexity: O(n + m), where n is the length of nums1 and m is the length of nums2. Space Complexity: O(n + m) due to storage of both sets.

Try this approach in the editor →

Approach 2: Approach 2: Using Brute Force with Optimizations

This approach iterates through each element of nums1 and checks for its existence in nums2 and vice-versa, leveraging constraints to optimize comparisons.

This solution utilizes Python's in keyword which naturally translates to a linear search within the list, and uses list comprehension for concise implementation.

Code

PythonJavaScriptJavaC#C++C

Python

JavaScript

Java

C#

C++

C

Complexity

Time Complexity: O(n * m) in worst case without optimizations; however, it's generally fast due to input size constraints. Space Complexity: O(1).

Try this approach in the editor →

Approach 3: 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.

Next, we create an array ans of length 2, where ans[0] represents the number of elements in nums1 that appear in s2, and ans[1] represents the number of elements in nums2 that appear in s1.

Then, we traverse each element x in the array nums1. If x has appeared in s2, we increment ans[0]. After that, we traverse each element x in the array nums2. If x has appeared in s1, we increment ans[1].

Finally, we return the array ans.

The time complexity is O(n + m), and the space complexity is O(n + m). Here, n and m are the lengths of the arrays nums1 and nums2 respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Set for Efficient Look-Up

Time Complexity: O(n + m), where n is the length of nums1 and m is the length of nums2. Space Complexity: O(n + m) due to storage of both sets.

Approach 2: Using Brute Force with Optimizations

Time Complexity: O(n * m) in worst case without optimizations; however, it's generally fast due to input size constraints. Space Complexity: O(1).

Hash Table or Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Nested LoopsO(n * m)O(1)Useful for small arrays or when minimizing extra memory is required
Hash Set Look-UpO(n + m)O(n + m)Best general solution when fast membership checks are needed

Video Solution

Leetcode | 2956. Find Common Elements Between Two Arrays | Easy | Java Solution • Developer Docs • 1,515 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Common Elements Between Two Arrays easy or hard?
LeetCode classifies this problem as Easy. The main idea is recognizing that repeated membership checks should use a hash set instead of nested loops. Once you apply the set approach, the implementation is straightforward.
Find Common Elements Between Two Arrays Python/Java solution
Most implementations build sets from both arrays and perform membership checks. Python uses the built‑in set type, Java uses HashSet, C++ uses unordered_set, and JavaScript uses Set. The algorithm logic remains the same across languages with O(n + m) time complexity.
How to solve Find Common Elements Between Two Arrays in O(n)?
Use a hash set for fast lookups. Insert elements of nums1 into one set and nums2 into another. Then iterate through each array and check if the current value exists in the opposite set. Each lookup is O(1) on average, so the total runtime becomes O(n + m).
What is the best approach for Find Common Elements Between Two Arrays?
The hash set approach is the most efficient solution. Convert both arrays into sets and check membership while iterating through the original arrays. Hash lookups run in average O(1) time, giving an overall complexity of O(n + m) with O(n + m) extra space.
Is Find Common Elements Between Two Arrays asked at Google/Amazon/Meta?
Array and hash table lookup problems like this appear frequently in technical interviews at companies such as Amazon, Google, and Meta. The problem tests your ability to recognize when a hash set can replace repeated linear searches.
What data structure is used in Find Common Elements Between Two Arrays?
The key data structure is a hash set. It stores elements from one array and allows constant‑time membership checks while scanning the other array. This reduces repeated comparisons and improves the runtime from O(n * m) to O(n + m).
What is the time complexity of Find Common Elements Between Two Arrays?
The optimal solution runs in O(n + m) time, where n and m are the lengths of the two arrays. Each array is processed once, and membership checks use constant‑time hash lookups. A brute force solution requires O(n * m) time due to nested comparisons.

Ready to solve this problem?

Practice Find Common Elements Between Two Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays