Intersection of Two Arrays solution and explanation
Google
Infosys
9 more videos on this problem
Intersection of Two Arrays - Leetcode 349 - PythonNeetCodeIO · 4:23 · 33K views
349. Intersection of Two Arrays | 4 Approaches | Sorting | 2 Pointer | Hash Set | Binary SearchAryan Mittal · 12:11 · 13K views
LeetCode 349 | Intersection of Two Arrays | Solution Explained (Java)Xavier Elon · 4:52 · 6K views
LeetCode 349: Intersection of Two Arrays - Interview Prep Ep 49Fisher Coder · 16:40 · 6K views
Leetcode | 349. Intersection of Two Arrays | Easy | Java SolutionDeveloper Docs · 6:38 · 3K views
LeetCode#349 Intersection of Two Arrays - PythonCodeJulian · 1:01 · 726 views
Intersection of two arrays - leetcode 349Algorial · 7:04 · 708 views
LeetCode 349. Intersection of Two Arrays JavaScript SolutionLearn Code · 1:10 · 400 views
Can You Find the Intersection of Two Arrays? (LeetCode 349: Intersection of Two Arrays)Code With Zi · 3:47 · 325 views
Intersection of Two Arrays - LeetCode 349 ExplainedAlvin The Programmer · 8:50 · 291 views
The problem
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4] Explanation: [4,9] is also accepted.
Constraints:
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
Approach overview
Problem Overview: You receive two integer arrays and must return their intersection. The result should contain only unique values that appear in both arrays, and the order does not matter.
Approach 1: Using Hash Sets (O(m + n) time, O(m + n) space)
This is the most direct solution. Insert all elements of the first array into a hash set, then iterate through the second array and check whether each value exists in the set. If the lookup succeeds, add it to a result set to ensure uniqueness. Hash lookups run in average O(1) time, so the overall complexity becomes linear relative to the total number of elements. This approach works well for unsorted inputs and demonstrates practical use of a hash table to eliminate duplicates efficiently.
The key insight is that sets automatically handle uniqueness. Instead of manually checking whether a value was already added, the set structure guarantees that duplicates are ignored. In interviews, this approach is usually the first optimized solution candidates present because it is easy to reason about and scales well for large arrays.
Approach 2: Sorting and Two Pointers (O(m log m + n log n) time, O(1) extra space)
If modifying the arrays is allowed, sorting both arrays enables a pointer-based scan. First sort the arrays using any efficient sorting algorithm. Then place one pointer at the start of each array and move them forward depending on the comparison of the current values. When the numbers match, add the value to the result and advance both pointers while skipping duplicates.
This approach relies on the idea that once arrays are sorted, equal elements align naturally during a linear scan. The two pointers technique avoids nested loops and reduces comparison overhead. The total runtime is dominated by the sorting step, which is O(m log m + n log n). The scan itself runs in O(m + n). This technique is common in problems involving sorted arrays and belongs to the broader family of sorting-based optimizations.
Recommended for interviews: The hash set solution is typically expected because it achieves optimal O(m + n) time and is easy to implement in languages like Python, Java, or C++. The sorting + two pointers method is still valuable to discuss. It shows you understand alternative strategies and how pointer techniques reduce comparisons when working with ordered data.
Approach 1: Using Hash Sets
This approach utilizes hash sets to efficiently track and identify unique intersections between the two arrays. By converting one of the arrays into a set, we can check for existence of elements in constant time, and we store intersections in another set to ensure uniqueness.
def intersection(nums1, nums2):
set1 = set(nums1)
resultSet = set()
for num in nums2:
if num in set1:
resultSet.add(num)
return list(resultSet)
nums1 = [4, 9, 5]
nums2 = [9, 4, 9, 8, 4]
result = intersection(nums1, nums2)
print(result)import java.util.HashSet;
import java.util.Set;
public class Intersection {
public static int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
Set<Integer> resultSet = new HashSet<>();
for (int num : nums1) {
set1.add(num);
}
for (int num : nums2) {
if (set1.contains(num)) {
resultSet.add(num);
}
}
int[] result = new int[resultSet.size()];
int i = 0;
for (int num : resultSet) {
result[i++] = num;
}
return result;
}
public static void main(String[] args) {
int[] nums1 = {4, 9, 5};
int[] nums2 = {9, 4, 9, 8, 4};
int[] result = intersection(nums1, nums2);
for (int num : result) {
System.out.print(num + " ");
}
}
}#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> set1(nums1.begin(), nums1.end());
unordered_set<int> resultSet;
for (int num : nums2) {
if (set1.count(num)) {
resultSet.insert(num);
}
}
return vector<int>(resultSet.begin(), resultSet.end());
}
int main() {
vector<int> nums1 = {4, 9, 5};
vector<int> nums2 = {9, 4, 9, 8, 4};
vector<int> result = intersection(nums1, nums2);
for (int num : result) {
cout << num << " ";
}
return 0;
}function intersection(nums1, nums2) {
let set1 = new Set(nums1);
let resultSet = new Set();
for (let num of nums2) {
if (set1.has(num)) {
resultSet.add(num);
}
}
return Array.from(resultSet);
}
let nums1 = [4, 9, 5];
let nums2 = [9, 4, 9, 8, 4];
let result = intersection(nums1, nums2);
console.log(result);#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// A simple hash function for integers
int hash(int value, int size) {
return abs(value) % size;
}
// Set data structure
typedef struct Set {
int *data;
int size;
int capacity;
} Set;
Set* createSet(int capacity) {
Set *set = (Set*)malloc(sizeof(Set));
set->data = (int*)calloc(capacity, sizeof(int));
set->size = 0;
set->capacity = capacity;
return set;
}
void add(Set *set, int value) {
int index = hash(value, set->capacity);
while (set->data[index] != 0) {
if (set->data[index] == value) return; // already present, do nothing
index = (index + 1) % set->capacity;
}
// Insert new value
set->data[index] = value;
set->size++;
}
bool contains(Set *set, int value) {
int index = hash(value, set->capacity);
while (set->data[index] != 0) {
if (set->data[index] == value) return true;
index = (index + 1) % set->capacity;
}
return false;
}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
Set *set1 = createSet(1009); // A prime number close to 1000
Set *resultSet = createSet(1009);
for (int i = 0; i < nums1Size; i++) {
add(set1, nums1[i]);
}
for (int j = 0; j < nums2Size; j++) {
if (contains(set1, nums2[j])) {
add(resultSet, nums2[j]);
}
}
int *result = (int *)malloc(resultSet->size * sizeof(int));
int index = 0;
for (int i = 0; i < resultSet->capacity; i++) {
if (resultSet->data[i] != 0) {
result[index++] = resultSet->data[i];
}
}
*returnSize = index;
return result;
}
int main() {
int nums1[] = {4, 9, 5};
int nums2[] = {9, 4, 9, 8, 4};
int returnSize;
int* result = intersection(nums1, 3, nums2, 5, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
class Intersection {
public static int[] IntersectionOfArrays(int[] nums1, int[] nums2) {
HashSet<int> set1 = new HashSet<int>(nums1);
HashSet<int> resultSet = new HashSet<int>();
foreach (int num in nums2) {
if (set1.Contains(num)) {
resultSet.Add(num);
}
}
int[] result = new int[resultSet.Count];
resultSet.CopyTo(result);
return result;
}
static void Main() {
int[] nums1 = {4, 9, 5};
int[] nums2 = {9, 4, 9, 8, 4};
int[] result = IntersectionOfArrays(nums1, nums2);
Console.WriteLine(string.Join(" ", result));
}
}This Python solution leverages Python's native set data structure to perform the intersection. It stores nums1 in a set and then iterates through nums2, checking for presence in set1 and adding to resultSet for the results.
Time complexity is O(n + m), and space complexity is O(n + m) due to the use of two sets.
Approach 2: Using Sorting and Two Pointers
This approach sorts both arrays and uses two pointers to identify the intersection. The sorted order ensures that we can efficiently find common elements in a single pass through both arrays.
def intersection(nums1, nums2):
nums1.sort()
nums2.sort()
i, j = 0, 0
result = []
while i < len(nums1) and j < len(nums2):
if nums1[i] < nums2[j]:
i += 1
elif nums1[i] > nums2[j]:
j += 1
else:
if not result or result[-1] != nums1[i]:
result.append(nums1[i])
i += 1
j += 1
return result
nums1 = [4, 9, 5]
nums2 = [9, 4, 9, 8, 4]
result = intersection(nums1, nums2)
print(result)import java.util.Arrays;
public class Intersection {
public static int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0, j = 0;
int[] tempResult = new int[nums1.length + nums2.length];
int index = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
if (index == 0 || tempResult[index - 1] != nums1[i]) {
tempResult[index++] = nums1[i];
}
i++;
j++;
}
}
return Arrays.copyOfRange(tempResult, 0, index);
}
public static void main(String[] args) {
int[] nums1 = {4, 9, 5};
int[] nums2 = {9, 4, 9, 8, 4};
int[] result = intersection(nums1, nums2);
for (int num : result) {
System.out.print(num + " ");
}
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
vector<int> result;
int i = 0, j = 0;
while (i < nums1.size() && j < nums2.size()) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
if (result.empty() || result.back() != nums1[i]) {
result.push_back(nums1[i]);
}
i++;
j++;
}
}
return result;
}
int main() {
vector<int> nums1 = {4, 9, 5};
vector<int> nums2 = {9, 4, 9, 8, 4};
vector<int> result = intersection(nums1, nums2);
for (int num : result) {
cout << num << " ";
}
return 0;
}function intersection(nums1, nums2) {
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b);
let i = 0, j = 0;
let result = [];
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
if (result.length === 0 || result[result.length - 1] !== nums1[i]) {
result.push(nums1[i]);
}
i++;
j++;
}
}
return result;
}
let nums1 = [4, 9, 5];
let nums2 = [9, 4, 9, 8, 4];
let result = intersection(nums1, nums2);
console.log(result);#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
qsort(nums1, nums1Size, sizeof(int), cmpfunc);
qsort(nums2, nums2Size, sizeof(int), cmpfunc);
int i = 0, j = 0;
int* result = (int*)malloc(sizeof(int) * (nums1Size < nums2Size ? nums1Size : nums2Size));
*returnSize = 0;
while (i < nums1Size && j < nums2Size) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
if (*returnSize == 0 || result[*returnSize - 1] != nums1[i]) {
result[(*returnSize)++] = nums1[i];
}
i++;
j++;
}
}
return result;
}
int main() {
int nums1[] = {4, 9, 5};
int nums2[] = {9, 4, 9, 8, 4};
int returnSize;
int* result = intersection(nums1, 3, nums2, 5, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
return 0;
}using System;
class Intersection {
public static int[] IntersectionOfArrays(int[] nums1, int[] nums2) {
Array.Sort(nums1);
Array.Sort(nums2);
int i = 0, j = 0;
int[] tempResult = new int[nums1.Length + nums2.Length];
int index = 0;
while (i < nums1.Length && j < nums2.Length) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
if (index == 0 || tempResult[index - 1] != nums1[i]) {
tempResult[index++] = nums1[i];
}
i++;
j++;
}
}
int[] result = new int[index];
Array.Copy(tempResult, 0, result, 0, index);
return result;
}
static void Main() {
int[] nums1 = {4, 9, 5};
int[] nums2 = {9, 4, 9, 8, 4};
int[] result = IntersectionOfArrays(nums1, nums2);
Console.WriteLine(string.Join(" ", result));
}
}This Python solution sorts the arrays and utilizes two indices to traverse them. It collects common elements uniquely by checking the last added element in the result list before appending.
Time complexity is O(n log n + m log m) due to sorting, where n and m are sizes of nums1 and nums2. Space complexity is O(n + m) for storing sorted arrays and results.
Approach 3: Hash Table or Array
First, we use a hash table or an array s of length 1001 to record the elements that appear in the array nums1. Then, we iterate through each element in the array nums2. If an element x is in s, we add x to the answer and remove x from s.
After the iteration is finished, we return the answer array.
The time complexity is O(n+m), and the space complexity is O(n). Here, n and m are the lengths of the arrays nums1 and nums2, respectively.
function intersection(nums1: number[], nums2: number[]): number[] {
const s = new Set(nums1);
return [...new Set(nums2.filter(x => s.has(x)))];
}func intersection(nums1 []int, nums2 []int) (ans []int) {
s := [1001]bool{}
for _, x := range nums1 {
s[x] = true
}
for _, x := range nums2 {
if s[x] {
ans = append(ans, x)
s[x] = false
}
}
return
}class Solution {
/**
* @param Integer[] $nums1
* @param Integer[] $nums2
* @return Integer[]
*/
function intersection($nums1, $nums2) {
$s1 = array_unique($nums1);
$s2 = array_unique($nums2);
$ans = array_intersect($s1, $s2);
return array_values($ans);
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Hash Sets | Time complexity is O(n + m), and space complexity is O(n + m) due to the use of two sets. |
| Using Sorting and Two Pointers | Time complexity is O(n log n + m log m) due to sorting, where n and m are sizes of nums1 and nums2. Space complexity is O(n + m) for storing sorted arrays and results. |
| Hash Table or Array | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Set Lookup | O(m + n) | O(m + n) | General case for unsorted arrays; fastest average solution |
| Sorting + Two Pointers | O(m log m + n log n) | O(1) | When arrays can be sorted and memory usage must stay minimal |
| Sorting + Binary Search | O(m log n) | O(1) | When one array is sorted and repeated binary searches are acceptable |
Frequently asked questions
Is Intersection of Two Arrays easy or hard?
Intersection of Two Arrays is classified as an Easy problem. It mainly tests familiarity with sets, basic array traversal, and simple algorithmic optimization.
Intersection of Two Arrays Python/Java solution
In Python, the solution often uses the built-in set type for O(1) lookups. In Java, developers typically use HashSet to store elements and check membership while scanning the second array.
How to solve Intersection of Two Arrays in O(n)?
Use a hash set to store elements from the first array. Iterate through the second array and perform constant-time set lookups. If the element exists, insert it into a result set to keep values unique. This produces an O(m + n) solution.
What is the best approach for Intersection of Two Arrays?
The hash set approach is generally considered the best solution. Insert elements of one array into a set and check membership while scanning the second array. This produces the intersection in O(m + n) time with O(m + n) space and avoids duplicate results.
Is Intersection of Two Arrays asked at Google/Amazon/Meta?
Intersection-style array problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants test knowledge of hash tables, two pointers, and efficient duplicate handling.
What data structure is used in Intersection of Two Arrays?
The most common data structure is a hash set (or hash table). It allows constant-time membership checks and automatically handles duplicates, which simplifies the intersection logic.
What is the time complexity of Intersection of Two Arrays?
The optimal solution runs in O(m + n) time using a hash set, where m and n are the lengths of the two arrays. Sorting-based solutions take O(m log m + n log n) because of the sorting step before applying two pointers.