Find Common Elements Between Two Arrays in Java (HashSet Method)

How to Find Common Elements Between Two Arrays in Java

Finding common elements between two arrays, also known as finding the intersection, is a common programming task. It is useful in scenarios such as comparing user lists, matching product IDs, or identifying shared records between two datasets. This guide covers the brute-force approach, the recommended HashSet solution, retainAll(), and the efficient two-pointer technique for sorted arrays.

Problem Statement

Given two arrays:

{1, 2, 3, 4, 5}

{3, 4, 5, 6, 7}

Find the elements that are present in both arrays:

{3, 4, 5}

Method 1: Brute Force (Nested Loops)

int[] array1 = {1, 2, 3, 4, 5};
int[] array2 = {3, 4, 5, 6, 7};

for (int i = 0; i < array1.length; i++) {
    for (int j = 0; j < array2.length; j++) {
        if (array1[i] == array2[j]) {
            System.out.println("Common: " + array1[i]);
            break;
        }
    }
}

This method compares every element of the first array with every element of the second array.

Although simple, it has O(n × m) time complexity, making it inefficient for large arrays.

Method 2: Using HashSet (Recommended)

import java.util.HashSet;
import java.util.Set;

int[] array1 = {1, 2, 3, 4, 5};
int[] array2 = {3, 4, 5, 6, 7};

Set<Integer> set1 = new HashSet<>();

for (int num : array1) {
    set1.add(num);
}

Set<Integer> common = new HashSet<>();

for (int num : array2) {
    if (set1.contains(num)) {
        common.add(num);
    }
}

System.out.println("Common elements: " + common);

This is the standard solution.

The first array is stored in a HashSet, allowing average O(1) lookup time. The second array is then scanned once to identify common values.

Overall complexity becomes O(n + m).

Method 3: Using retainAll()

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
Set<Integer> set2 = new HashSet<>(Arrays.asList(3, 4, 5, 6, 7));

set1.retainAll(set2);

System.out.println(set1);

retainAll() removes every element that is not present in the specified collection.

After execution, set1 contains only the common elements.

Method 4: Two-Pointer Technique (Sorted Arrays)

If both arrays are already sorted, a two-pointer approach avoids using extra memory.

int[] array1 = {1, 2, 3, 4, 5};
int[] array2 = {3, 4, 5, 6, 7};

int i = 0;
int j = 0;

while (i < array1.length && j < array2.length) {

    if (array1[i] == array2[j]) {
        System.out.println("Common: " + array1[i]);
        i++;
        j++;
    } else if (array1[i] < array2[j]) {
        i++;
    } else {
        j++;
    }
}

This algorithm runs in O(n + m) time while using only O(1) extra space.

Step-by-Step Explanation

Brute Force

Each element of the first array is compared with every element of the second array.

Whenever a match is found, it is printed.

HashSet Method

All elements from the first array are inserted into a HashSet.

Each element from the second array is checked using contains().

Matching elements are stored in another set to avoid duplicates.

Two-Pointer Technique

Both arrays are traversed simultaneously.

• If both values match, the element is common.
• If the first value is smaller, move the first pointer.
• Otherwise, move the second pointer.

Since both arrays are sorted, no comparisons are wasted.

Internal Working (Memory View)

For:

Array 1 = {1, 2, 3, 4, 5}

Array 2 = {3, 4, 5, 6, 7}

Processing:

i = 0 (1), j = 0 (3)

1 < 3 → move i

i = 1 (2)

2 < 3 → move i

i = 2 (3)

3 == 3 → Common

i = 3, j = 1

4 == 4 → Common

i = 4, j = 2

5 == 5 → Common

i reaches end

Result = {3, 4, 5}

Real-Life Analogy

Imagine comparing two guest lists to find people invited to both events.

Instead of checking every name from one list against every name in the other, you first write all names from the first list onto a board. Then, as you read the second list, you simply check whether each name already exists on the board. This is exactly how the HashSet approach works.

Best Practices

• Use a HashSet for general-purpose intersection of unsorted arrays.
• Use the two-pointer approach when both arrays are already sorted.
• Use retainAll() when working directly with Set collections and concise code is preferred.
• Store results in a Set if duplicate common elements should be removed automatically.

Common Mistakes

1. Using nested loops for large arrays, resulting in poor performance.
2. Applying the two-pointer technique to unsorted arrays.
3. Printing duplicate common elements when the arrays contain repeated values.
4. Confusing intersection (common elements) with union (all unique elements).

Expert Tips

• retainAll() modifies the calling set. Create a copy first if you need to preserve the original data.
• The two-pointer algorithm is closely related to the merge step used in Merge Sort.
• To compute the union of two arrays instead of the intersection, use addAll() with a Set.

Comparison Table

Frequently Asked Questions

What is the most efficient way to find common elements in two unsorted arrays?

The HashSet approach is the most efficient general-purpose solution, running in O(n + m) time.

Does the two-pointer technique work on unsorted arrays?

No. It requires both arrays to be sorted.

What does retainAll() do?

retainAll() keeps only the elements that are also present in another collection, effectively computing the intersection.

How can I avoid modifying the original set when using retainAll()?

Create a copy first:

Set<Integer> result = new HashSet<>(set1);
result.retainAll(set2);

Can I find common elements among more than two arrays?

Yes. Repeatedly apply the same intersection logic with each additional array.

What is the difference between intersection and union?

Intersection returns only elements common to both arrays, while union returns every distinct element present in either array.

Is the brute-force approach ever useful?

Yes. It is suitable for learning purposes or very small datasets, but not for large inputs.

Can I find common elements between arrays of String objects?

Yes. The same techniques work for String arrays because HashSet and retainAll() are generic and rely on equals() and hashCode().