🔍 Find the Intersection of Two Arrays in DSA

When working with arrays, one common problem in Data Structures and Algorithms (DSA) is to find the intersection — i.e., elements that appear in both arrays.

For example, if you have two lists of numbers, you might want to find out which numbers are common to both. This is a common question in coding interviews, and it helps you strengthen your logic-building skills.

💡 What Is the Intersection of Two Arrays?

The intersection of two arrays means the set of elements that appear in both arrays.

Example

Array A = [1, 2, 3, 4, 5]
Array B = [3, 4, 5, 6, 7]

✅ Intersection = [3, 4, 5]

These numbers are present in both arrays A and B.

⚙️ Approach 1. Brute Force (Simple but Less Efficient)

🧠 Logic

For each element in array A, check whether it exists in array B.
If yes, add it to the intersection list.

⏱️ Time Complexity: O(n²)

💾 Space Complexity: O(1)

💻 C++ Code Example

#include <iostream>using namespace std;

int main() {
    int A[] = {1, 2, 3, 4, 5};
    int B[] = {3, 4, 5, 6, 7};
    int n = 5, m = 5;

    cout << "Intersection: ";
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(A[i] == B[j]) {
                cout << A[i] << " ";
                break;
            }
        }
    }
    return 0;
}

✅ Output

Intersection: 3 4 5

⚡ Approach 2. Using Hashing (Efficient and Common)

🧠 Logic

Store all elements of the first array in a hash set.
Traverse the second array, and check if an element exists in the set.
If yes, add it to the intersection.

⏱️ Time Complexity: O(n + m)

💾 Space Complexity: O(n)

💻 C++ Code Example

#include <iostream>#include <unordered_set>using namespace std;

int main() {
    int A[] = {1, 2, 3, 4, 5};
    int B[] = {3, 4, 5, 6, 7};
    int n = 5, m = 5;

    unordered_set<int> s(A, A + n);
    cout << "Intersection: ";

    for (int i = 0; i < m; i++) {
        if (s.find(B[i]) != s.end()) {
            cout << B[i] << " ";
            s.erase(B[i]); // to avoid duplicates
        }
    }
    return 0;
}

✅ Output

Intersection: 3 4 5

🌟 Why Use Hashing?

Hashing provides O(1) average lookup time, making it much faster than the brute-force method, especially for large datasets.

🚀 Approach 3. Two-Pointer Technique (When Arrays Are Sorted)

🧠 Logic

Sort both arrays if not sorted.
Use two pointers — one for each array.
Compare elements:
- If A[i] == B[j], add to intersection and move both pointers.
- If A[i] < B[j], move i forward.
- Else, move j forward.

⏱️ Time Complexity: O(n + m)

💾 Space Complexity: O(1)

💻 C++ Code Example

#include <iostream>#include <algorithm>using namespace std;

int main() {
    int A[] = {1, 2, 3, 4, 5};
    int B[] = {3, 4, 5, 6, 7};
    int n = 5, m = 5;

    int i = 0, j = 0;

    cout << "Intersection: ";
    while (i < n && j < m) {
        if (A[i] == B[j]) {
            cout << A[i] << " ";
            i++;
            j++;
        }
        else if (A[i] < B[j])
            i++;
        else
            j++;
    }
    return 0;
}

✅ Output

Intersection: 3 4 5

📊 Comparison Table

Approach	Time Complexity	Space Complexity	Suitable For
Brute Force	O(n²)	O(1)	Small arrays
Hashing	O(n + m)	O(n)	Unsorted arrays
Two Pointer	O(n + m)	O(1)	Sorted arrays

🧠 Real-Life Use Case

Finding common friends between two users on social media.
Identifying common customers between two databases.
Comparing tags or keywords shared between two documents.

🏁 Conclusion

Finding the intersection of two arrays is a fundamental DSA problem that strengthens your understanding of searching, hashing, and sorting.

Start with the brute force approach for clarity.
Then move to hashing or two-pointer for efficiency.

Mastering these methods will help you in technical interviews, especially for roles involving data structures and algorithms.