.png)
Find Intersection of Two Arrays
Problem Statement
Given two arrays, find their intersection.
The intersection of two arrays consists of:
- Elements that are present in both arrays
- Each common element should appear only once in the result, even if it appears multiple times in the input arrays
The order of elements is not important unless explicitly mentioned.
Example 1
Input
arr1 = [1, 2, 3, 4]
arr2 = [3, 4, 5, 6]
Output
[3, 4]
Example 2
Input
arr1 = [1, 2, 2, 3]
arr2 = [2, 2, 4]
Output
[2]
Why This Problem Is Important
This is a frequently asked array interview problem because it:
- Tests understanding of duplicate handling
- Introduces hashing and set concepts
- Helps build logic for:
- Set operations
- Data filtering
- Comparing datasets
This problem also acts as a foundation for:
- Union of arrays
- Difference of arrays
- Symmetric difference problems
Approaches to Solve the Problem
- Brute Force Approach
- Using Hashing (Best and Most Efficient)
- Sorting + Two Pointers (For Sorted Arrays)
Approach 1: Brute Force Method
Idea
- Compare each element of the first array with every element of the second array
- If elements match, add them to the result
- Ensure duplicates are not added more than once
Algorithm
- Create an empty result array
- Loop through arr1
- For each element in arr1, loop through arr2
- If elements are equal:
- Check if the element already exists in result
- Add it if not present
- Print the result array
Time and Space Complexity
- Time Complexity: O(n × m)
- Space Complexity: O(k)
(where k is the number of common elements)
C Implementation
#include<stdio.h>
int main() {
int arr1[] = {1, 2, 2, 3};
int arr2[] = {2, 2, 4};
int n1 = 4, n2 = 3;
int result[10];
int k = 0;
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
if (arr1[i] == arr2[j]) {
int found = 0;
for (int x = 0; x < k; x++) {
if (result[x] == arr1[i]) {
found = 1;
break;
}
}
if (!found) {
result[k++] = arr1[i];
}
}
}
}
printf("Intersection: ");
for (int i = 0; i < k; i++)
printf("%d ", result[i]);
return 0;
}
C++ Implementation
#include<iostream>
using namespace std;
int main() {
int arr1[] = {1, 2, 2, 3};
int arr2[] = {2, 2, 4};
int n1 = 4, n2 = 3;
int result[10];
int k = 0;
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
if (arr1[i] == arr2[j]) {
bool found = false;
for (int x = 0; x < k; x++) {
if (result[x] == arr1[i]) {
found = true;
break;
}
}
if (!found) {
result[k++] = arr1[i];
}
}
}
}
cout << "Intersection: ";
for (int i = 0; i < k; i++)
cout << result[i] << " ";
return 0;
}
Java Implementation
public class IntersectionBruteForce {
public static void main(String[] args) {
int[] arr1 = {1, 2, 2, 3};
int[] arr2 = {2, 2, 4};
int[] result = new int[10];
int k = 0;
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr2.length; j++) {
if (arr1[i] == arr2[j]) {
boolean found = false;
for (int x = 0; x < k; x++) {
if (result[x] == arr1[i]) {
found = true;
break;
}
}
if (!found) {
result[k++] = arr1[i];
}
}
}
}
System.out.print("Intersection: ");
for (int i = 0; i < k; i++)
System.out.print(result[i] + " ");
}
}
Python Implementation
arr1 = [1, 2, 2, 3]
arr2 = [2, 2, 4]
result = []
for i in arr1:
for j in arr2:
if i == j and i not in result:
result.append(i)
print("Intersection:", result)
JavaScript Implementation
let arr1 = [1, 2, 2, 3];
let arr2 = [2, 2, 4];
let result = [];
for (let i = 0; i < arr1.length; i++) {
for (let j = 0; j < arr2.length; j++) {
if (arr1[i] === arr2[j] && !result.includes(arr1[i])) {
result.push(arr1[i]);
}
}
}
console.log("Intersection:", result);
Approach 2: Using Hashing (Recommended)
Idea
- Store elements of the first array in a hash set
- Traverse the second array
- If an element exists in the set:
- Add it to the result
- Remove it from the set to avoid duplicates
Algorithm
- Insert all elements of arr1 into a hash set
- Traverse arr2
- If current element exists in the set:
- Print or store it
- Remove it from the set
Time and Space Complexity
- Time Complexity: O(n + m)
- Space Complexity: O(n)
C++ Implementation
#include<iostream>
#include<unordered_set>
using namespace std;
int main() {
int arr1[] = {1, 2, 3, 4};
int arr2[] = {3, 4, 5, 6};
unordered_set s(arr1, arr1 + 4);
cout << "Intersection: ";
for (int x : arr2) {
if (s.find(x) != s.end()) {
cout << x << " ";
s.erase(x);
}
}
return 0;
}
Output
Intersection: 3 4
Java Implementation
import java.util.*;
public class IntersectionArray {
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 4};
int[] arr2 = {3, 4, 5, 6};
Set set = new HashSet<>();
for (int x : arr1)
set.add(x);
Set result = new HashSet<>();
for (int x : arr2) {
if (set.contains(x))
result.add(x);
}
System.out.println("Intersection: " + result);
}
}
Output
Intersection: [3, 4]
Python Implementation
arr1 = [1, 2, 3, 4]
arr2 = [3, 4, 5, 6]
intersection = list(set(arr1) & set(arr2))
print("Intersection:", intersection)
Output
Intersection: [3, 4]
JavaScript Implementation
let arr1 = [1, 2, 3, 4];
let arr2 = [3, 4, 5, 6];
let set1 = new Set(arr1);
let result = [];
for (let x of arr2) {
if (set1.has(x)) {
result.push(x);
set1.delete(x);
}
}
console.log("Intersection:", result);
Output
Intersection: [3, 4]
Approach 3: Sorting + Two Pointers (For Sorted Arrays)
Idea
- Sort both arrays
- Use two pointers to compare elements
- Move pointers based on comparison
- Skip duplicates
Time and Space Complexity
- Time Complexity: O(n log n + m log m)
- Space Complexity: O(1) (excluding output)
Approach 3: Sorting + Two Pointers
C Implementation
#include<stdio.h>
int main() {
int arr1[] = {1, 2, 2, 3};
int arr2[] = {2, 2, 4};
int n1 = 4, n2 = 3;
// Sort arr1
for (int i = 0; i < n1 - 1; i++) {
for (int j = i + 1; j < n1; j++) {
if (arr1[i] > arr1[j]) {
int temp = arr1[i];
arr1[i] = arr1[j];
arr1[j] = temp;
}
}
}
// Sort arr2
for (int i = 0; i < n2 - 1; i++) {
for (int j = i + 1; j < n2; j++) {
if (arr2[i] > arr2[j]) {
int temp = arr2[i];
arr2[i] = arr2[j];
arr2[j] = temp;
}
}
}
int i = 0, j = 0;
int lastPrinted = -1;
printf("Intersection: ");
while (i < n1 && j < n2) {
if (arr1[i] == arr2[j]) {
if (arr1[i] != lastPrinted) {
printf("%d ", arr1[i]);
lastPrinted = arr1[i];
}
i++;
j++;
} else if (arr1[i] < arr2[j]) {
i++;
} else {
j++;
}
}
return 0;
}
C++ Implementation
#include<iostream>
#include <algorithm>
using namespace std;
int main() {
int arr1[] = {1, 2, 2, 3};
int arr2[] = {2, 2, 4};
int n1 = 4, n2 = 3;
sort(arr1, arr1 + n1);
sort(arr2, arr2 + n2);
int i = 0, j = 0;
int lastPrinted = -1;
cout << "Intersection: ";
while (i < n1 && j < n2) {
if (arr1[i] == arr2[j]) {
if (arr1[i] != lastPrinted) {
cout << arr1[i] << " ";
lastPrinted = arr1[i];
}
i++;
j++;
} else if (arr1[i] < arr2[j]) {
i++;
} else {
j++;
}
}
return 0;
}
Java Implementation
import java.util.Arrays;
public class IntersectionTwoPointers {
public static void main(String[] args) {
int[] arr1 = {1, 2, 2, 3};
int[] arr2 = {2, 2, 4};
Arrays.sort(arr1);
Arrays.sort(arr2);
int i = 0, j = 0;
Integer lastPrinted = null;
System.out.print("Intersection: ");
while (i < arr1.length && j < arr2.length) {
if (arr1[i] == arr2[j]) {
if (lastPrinted == null || arr1[i] != lastPrinted) {
System.out.print(arr1[i] + " ");
lastPrinted = arr1[i];
}
i++;
j++;
} else if (arr1[i] < arr2[j]) {
i++;
} else {
j++;
}
}
}
}
Python Implementation
arr1 = [1, 2, 2, 3]
arr2 = [2, 2, 4]
arr1.sort()
arr2.sort()
i = j = 0
result = []
while i < len(arr1) and j < len(arr2):
if arr1[i] == arr2[j]:
if not result or result[-1] != arr1[i]:
result.append(arr1[i])
i += 1
j += 1
elif arr1[i] < arr2[j]:
i += 1
else:
j += 1
print("Intersection:", result)
JavaScript Implementation
let arr1 = [1, 2, 2, 3];
let arr2 = [2, 2, 4];
arr1.sort((a, b) => a - b);
arr2.sort((a, b) => a - b);
let i = 0, j = 0;
let result = [];
while (i < arr1.length && j < arr2.length) {
if (arr1[i] === arr2[j]) {
if (result.length === 0 || result[result.length - 1] !== arr1[i]) {
result.push(arr1[i]);
}
i++;
j++;
} else if (arr1[i] < arr2[j]) {
i++;
} else {
j++;
}
}
console.log("Intersection:", result);
Summary
- Intersection includes only common elements
- Each element appears once
- Hashing provides the best performance
- Order is not guaranteed unless sorted
Key Takeaways
- Best Time Complexity: O(n + m)
- Avoid duplicates using sets
- Suitable for interview and real-world use cases
Next Problem in the Series
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
