Find Common Elements Between Two Arrays solution and explanation
Google
9 more videos on this problem
Leetcode | 2956. Find Common Elements Between Two Arrays | Easy | Java SolutionDeveloper Docs · 9:00 · 1K views
2956. Find Common Elements Between Two Arrayscode Explainer · 4:05 · 1K views
2956. Find Common Elements Between Two ArraysAyush Rao · 2:59 · 920 views
2956. Find Common Elements Between Two Arrays (Leetcode Easy)Programming Live with Larry · 2:37 · 480 views
2956. Find Common Elements Between Two Arrays | Leetcode 2956 |C++ | HindiWaytoCode · 5:24 · 468 views
LeetCode 2956 | Find Common Elements Between Two Arrays | JavaSleepy Cracker · 2:23 · 387 views
2956. Find Common Elements Between Two Arrays - Leetcode - Hashmap- C++ Tutorialcodetutorial4you · 8:05 · 271 views
leetcode 2956 Find Common Elements Between Two Arrays some conceptsCode-Yao · 9:59 · 110 views
Find Common Elements Between Two Arrays|leetcode -2956|Hashset|EASYMeni coding M&M · 7:17 · 94 views
my attempt at solving leetcode 2956: find common elements between two arrays [SOLVED]Cameron Late · 13:42 · 89 views
The problem
You are given two integer arrays nums1 and nums2 of sizes n and m, respectively. Calculate the following values:
answer1: the number of indicesisuch thatnums1[i]exists innums2.answer2: the number of indicesisuch thatnums2[i]exists innums1.
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.lengthm == nums2.length1 <= n, m <= 1001 <= 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.
def find_common_elements(nums1, nums2):
set_nums2 = set(nums2)
answer1 = sum(1 for num in nums1 if num in set_nums2)
set_nums1 = set(nums1)
answer2 = sum(1 for num in nums2 if num in set_nums1)
return [answer1, answer2]import java.util.*;
public class Solution {
public static int[] findCommonElements(int[] nums1, int[] nums2) {
Set<Integer> setNums2 = new HashSet<>();
for (int num : nums2) {
setNums2.add(num);
}
int answer1 = 0;
for (int num : nums1) {
if (setNums2.contains(num)) {
answer1++;
}
}
Set<Integer> setNums1 = new HashSet<>();
for (int num : nums1) {
setNums1.add(num);
}
int answer2 = 0;
for (int num : nums2) {
if (setNums1.contains(num)) {
answer2++;
}
}
return new int[]{answer1, answer2};
}
}#include <iostream>
#include <unordered_set>
#include <vector>
std::vector<int> findCommonElements(const std::vector<int>& nums1, const std::vector<int>& nums2) {
std::unordered_set<int> setNums2(nums2.begin(), nums2.end());
int answer1 = 0;
for(const int& num : nums1) {
if(setNums2.find(num) != setNums2.end()) {
answer1++;
}
}
std::unordered_set<int> setNums1(nums1.begin(), nums1.end());
int answer2 = 0;
for(const int& num : nums2) {
if(setNums1.find(num) != setNums1.end()) {
answer2++;
}
}
return {answer1, answer2};
}function findCommonElements(nums1, nums2) {
const setNums2 = new Set(nums2);
const answer1 = nums1.reduce((count, num) => count + (setNums2.has(num) ? 1 : 0), 0);
const setNums1 = new Set(nums1);
const answer2 = nums2.reduce((count, num) => count + (setNums1.has(num) ? 1 : 0), 0);
return [answer1, answer2];
}#include <stdio.h>
#include <stdbool.h>
#define MAX 101
bool exists_in_nums2[MAX] = {false};
bool exists_in_nums1[MAX] = {false};
void find_common_elements(int* nums1, int n1, int* nums2, int n2, int result[2]) {
for (int i = 0; i < n2; ++i) {
exists_in_nums2[nums2[i]] = true;
}
int answer1 = 0;
for (int i = 0; i < n1; ++i) {
if (exists_in_nums2[nums1[i]]) {
answer1++;
}
}
for (int i = 0; i < n1; ++i) {
exists_in_nums1[nums1[i]] = true;
}
int answer2 = 0;
for (int i = 0; i < n2; ++i) {
if (exists_in_nums1[nums2[i]]) {
answer2++;
}
}
result[0] = answer1;
result[1] = answer2;
}using System;
using System.Collections.Generic;
public class Solution {
public static int[] FindCommonElements(int[] nums1, int[] nums2) {
HashSet<int> setNums2 = new HashSet<int>(nums2);
int answer1 = 0;
foreach (int num in nums1) {
if (setNums2.Contains(num)) {
answer1++;
}
}
HashSet<int> setNums1 = new HashSet<int>(nums1);
int answer2 = 0;
foreach (int num in nums2) {
if (setNums1.Contains(num)) {
answer2++;
}
}
return new int[]{answer1, answer2};
}
}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.
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: 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.
def find_common_elements(nums1, nums2):
answer1 = sum(1 for num in nums1 if num in nums2)
answer2 = sum(1 for num in nums2 if num in nums1)
return [answer1, answer2]import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public static int[] findCommonElements(int[] nums1, int[] nums2) {
int answer1 = 0;
for (int num1 : nums1) {
if (Arrays.stream(nums2).anyMatch(num -> num == num1)) {
answer1++;
}
}
int answer2 = 0;
for (int num2 : nums2) {
if (Arrays.stream(nums1).anyMatch(num -> num == num2)) {
answer2++;
}
}
return new int[]{answer1, answer2};
}
}#include <iostream>
#include <vector>
std::vector<int> findCommonElements(const std::vector<int>& nums1, const std::vector<int>& nums2) {
int answer1 = 0;
for (const int& num1 : nums1) {
for (const int& num2 : nums2) {
if (num1 == num2) {
answer1++;
break;
}
}
}
int answer2 = 0;
for (const int& num2 : nums2) {
for (const int& num1 : nums1) {
if (num1 == num2) {
answer2++;
break;
}
}
}
return {answer1, answer2};
}function findCommonElements(nums1, nums2) {
let answer1 = nums1.filter(num => nums2.includes(num)).length;
let answer2 = nums2.filter(num => nums1.includes(num)).length;
return [answer1, answer2];
}#include <stdio.h>
int findCommonElements(int* nums1, int n1, int* nums2, int n2, int result[2]) {
int answer1 = 0;
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
if (nums1[i] == nums2[j]) {
answer1++;
break;
}
}
}
int answer2 = 0;
for (int i = 0; i < n2; i++) {
for (int j = 0; j < n1; j++) {
if (nums2[i] == nums1[j]) {
answer2++;
break;
}
}
}
result[0] = answer1;
result[1] = answer2;
}using System;
using System.Linq;
public class Solution {
public static int[] FindCommonElements(int[] nums1, int[] nums2) {
int answer1 = nums1.Count(num => nums2.Contains(num));
int answer2 = nums2.Count(num => nums1.Contains(num));
return new int[]{answer1, answer2};
}
}This solution utilizes Python's in keyword which naturally translates to a linear search within the list, and uses list comprehension for concise implementation.
Time Complexity: O(n * m) in worst case without optimizations; however, it's generally fast due to input size constraints. Space Complexity: O(1).
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.
function findIntersectionValues(nums1: number[], nums2: number[]): number[] {
const s1: number[] = Array(101).fill(0);
const s2: number[] = Array(101).fill(0);
for (const x of nums1) {
s1[x] = 1;
}
for (const x of nums2) {
s2[x] = 1;
}
const ans: number[] = Array(2).fill(0);
for (const x of nums1) {
ans[0] += s2[x];
}
for (const x of nums2) {
ans[1] += s1[x];
}
return ans;
}func findIntersectionValues(nums1 []int, nums2 []int) []int {
s1 := [101]int{}
s2 := [101]int{}
for _, x := range nums1 {
s1[x] = 1
}
for _, x := range nums2 {
s2[x] = 1
}
ans := make([]int, 2)
for _, x := range nums1 {
ans[0] += s2[x]
}
for _, x := range nums2 {
ans[1] += s1[x]
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Set for Efficient Look-Up | Time Complexity: O(n + m), where n is the length of |
| 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 | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Nested Loops | O(n * m) | O(1) | Useful for small arrays or when minimizing extra memory is required |
| Hash Set Look-Up | O(n + m) | O(n + m) | Best general solution when fast membership checks are needed |
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.