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

1. Brute Force Approach
2. Using Hashing (Best and Most Efficient)
3. 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

1. Create an empty result array
2. Loop through arr1
3. For each element in arr1, loop through arr2
4. If elements are equal:
   • Check if the element already exists in result
   • Add it if not present
5. 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 

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

1. Insert all elements of arr1 into a hash set
2. Traverse arr2
3. 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 
#include 
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 

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 
#include 
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

Sort an Array of 0s and 1s