Intersection of Two Arrays in Java, With and Without Duplicates

The intersection of two arrays contains the values that appear in both arrays, and in Java we compute it by putting one array into a HashSet and keeping the elements of the other array that the set contains. The JDK has no ready-made method for arrays, but Set.retainAll() and streams make the intersection a few lines long.

Typical uses are finding the mutual followers of two users, the products that two warehouses both stock, or the seat numbers that a new booking shares with existing ones.

The following example finds the values two int arrays have in common, in the order of the first array.

int[] a = {4, 1, 7, 4, 9};
int[] b = {9, 4, 2, 4};
Set<Integer> inB = Arrays.stream(b).boxed().collect(Collectors.toSet());
int[] common = Arrays.stream(a).filter(inB::contains).distinct().toArray();   // [4, 9]

The set gives each lookup constant time, so the whole intersection takes O(n + m) time. We also look at the version that keeps repeated matches, the retainAll() approach for object arrays, sorted input, and the quick check for any common element.

1. Common Values Once, or Every Matching Pair

Before writing code, we decide what happens to repeated values. A set intersection lists each common value once. A multiset intersection, also known from the LeetCode problem “Intersection of Two Arrays II”, keeps a value as many times as it appears in both arrays, which is the smaller of its two counts.

Most business code wants the set version, for example a list of mutual followers. The multiset version matters when the elements stand for quantities, such as order lines where each unit counts.

2. Intersection of Object Arrays with retainAll()

The method retainAll() removes every element from a collection that the argument collection does not contain. Calling it on a set built from the first array leaves only the common values. The set is changed in place, so we always start from a new set and never call retainAll() on a set that other code still uses.

For example, a social app shows the accounts that two users both follow. We keep the order of the first user’s list with a LinkedHashSet.

String[] aliceFollows = {"raj", "li", "tom", "ana"};
String[] bobFollows = {"ana", "sam", "li"};
Set<String> mutual = new LinkedHashSet<>(Arrays.asList(aliceFollows));
boolean changed = mutual.retainAll(new HashSet<>(Arrays.asList(bobFollows)));   // true
String[] both = mutual.toArray(String[]::new);                                  // [li, ana]

The argument of retainAll() should be a Set, because the method calls contains() on it once for every element of our set. With Arrays.asList(bobFollows) as the argument, each call is a linear search through the list, and the intersection becomes O(n x m). For two arrays of 100,000 names that is up to 10 billion comparisons instead of about 200,000 hash lookups.

The same code works for Integer[] and for any class with correct equals() and hashCode() methods, such as a record.

3. Common Elements of int Arrays with a Stream

Primitive arrays cannot go into Arrays.asList() as elements, because Arrays.asList(intArray) creates a List<int[]>. We therefore box only the array we search in, and stream the other array as an IntStream. The call distinct() removes repeated matches, and the result keeps the order of the first array.

static int[] intersect(int[] a, int[] b) {
    Set<Integer> lookup = new HashSet<>();
    for (int v : b) {
        lookup.add(v);
    }
    return Arrays.stream(a)
            .filter(lookup::contains)
            .distinct()
            .toArray();
}

int[] scoresA = {70, 85, 90, 85};
int[] scoresB = {85, 60, 70};
int[] shared = intersect(scoresA, scoresB);              // [70, 85]
int[] nothing = intersect(scoresA, new int[]{1, 2});     // []
int[] sortedShared = IntStream.of(intersect(new int[]{9, 3, 5}, new int[]{5, 9})).sorted().toArray();   // [5, 9]

We build the set from the smaller array when the sizes differ a lot, because that saves memory and the loop over the bigger array is a cheap sequence of lookups. A filter such as x -> Arrays.asList(b).contains(x) looks shorter, but it searches the whole second array for every element of the first one.

4. Keeping Repeated Matches with a Count Map

For the multiset intersection, a set is not enough, because it forgets how often a value appeared. We count the values of the second array in a Map, and every time the first array contains a value with a count above zero, we add the value to the result and lower its count by one.

static int[] intersectWithRepeats(int[] a, int[] b) {
    Map<Integer, Integer> counts = new HashMap<>();
    for (int v : b) {
        counts.merge(v, 1, Integer::sum);
    }
    int[] out = new int[Math.min(a.length, b.length)];
    int k = 0;
    for (int v : a) {
        Integer left = counts.get(v);
        if (left != null && left > 0) {
            counts.put(v, left - 1);
            out[k++] = v;
        }
    }
    return Arrays.copyOf(out, k);
}

int[] repeats = intersectWithRepeats(new int[]{4, 1, 7, 4, 9}, new int[]{9, 4, 2, 4});   // [4, 4, 9]
int[] oneMatch = intersectWithRepeats(new int[]{2, 2, 2}, new int[]{2});              // [2]

The method Map.merge() stores 1 for a new key and adds 1 to an existing count, so the counting loop needs no if statement. The result array cannot be longer than the shorter input, which is why Arrays.copyOf() trims it to the number of matches at the end.

5. Intersection of Two Sorted Arrays

Sorted input lets us skip the hash set entirely. Two indexes start at the beginning of both arrays, and the index pointing at the smaller value moves forward. When the two values are equal, the value is common, so we record it and move both indexes.

static int[] intersectSorted(int[] a, int[] b) {
    int[] out = new int[Math.min(a.length, b.length)];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length) {
        if (a[i] < b[j]) {
            i++;
        } else if (a[i] > b[j]) {
            j++;
        } else {
            if (k == 0 || out[k - 1] != a[i]) {
                out[k++] = a[i];          // skip repeats
            }
            i++;
            j++;
        }
    }
    return Arrays.copyOf(out, k);
}

int[] sortedCommon = intersectSorted(new int[]{1, 4, 4, 7, 9}, new int[]{2, 4, 4, 9});   // [4, 9]
int[] noOverlap = intersectSorted(new int[]{1, 2, 3}, new int[]{4, 5, 6});           // []

The loop stops as soon as one array runs out, so it takes at most O(n + m) steps and no extra memory besides the result. Removing the if around out[k++] = a[i] turns it into the multiset version, which returns [4, 4, 9] for the same input.

If the arrays arrive unsorted, we sort copies made with a.clone() and b.clone() instead of the caller’s arrays. Changing an input array is a side effect that surprises the caller, and the sorting costs O(n log n), so the hash approach from section 3 is the better default.

6. Checking for Any Common Element

Sometimes we do not need the common values, only the answer to whether there is at least one. A cinema booking service, for example, rejects a request when one of the requested seats is already booked. Building the full intersection for that check wastes work, because the answer is known at the first match.

Integer[] booked = {12, 13, 14};
Integer[] requested = {11, 12};
boolean clash = !Collections.disjoint(Arrays.asList(booked), Arrays.asList(requested));   // true
Set<Integer> bookedSet = Set.of(12, 13, 14);
boolean free = Arrays.stream(new int[]{20, 21}).noneMatch(bookedSet::contains);           // true

The method Collections.disjoint() returns true when the two collections have no element in common. Both versions stop at the first match, and the stream with anyMatch() or noneMatch() works on primitive arrays without boxing the searched array.

7. Comparing the Intersection Approaches

All approaches give the same set intersection, and they differ in speed, memory and their treatment of repeated values.

Approach	Input	Repeats in result	Time	Extra memory
retainAll() with a Set argument	Object arrays	Once	O(n + m)	O(n + m)
HashSet lookup + filter()	Primitive or object arrays	Once (with distinct())	O(n + m)	O(m)
Count map	Any	Smaller count	O(n + m)	O(m)
Two pointers	Sorted arrays	Once, or kept	O(n + m)	Only the result
retainAll() with a List argument	Object arrays	Once	O(n x m)	O(n)
Nested loops	Any	Depends on the code	O(n x m)	Only the result

8. Array Intersection FAQs

Readers who get the basic intersection working ask about more arrays, differences and letter case.

8.1. How do we find the intersection of more than two arrays?

We start with a set of the first array and call retainAll() once for each of the other arrays, each time with a set. After the last call, the set holds the values that every array contains.

String[] mon = {"ana", "li", "raj"};
String[] tue = {"li", "raj", "tom"};
String[] wed = {"raj", "li"};
Set<String> everyDay = new LinkedHashSet<>(Arrays.asList(mon));
boolean c1 = everyDay.retainAll(new HashSet<>(Arrays.asList(tue)));   // true
boolean c2 = everyDay.retainAll(new HashSet<>(Arrays.asList(wed)));   // false, nothing removed
String days = everyDay.toString();                                    // "[li, raj]"

8.2. How do we find the elements of one array that are not in the other?

We use removeAll() instead of retainAll(). The result is the difference A minus B, and the elements found in either array are the union of the two arrays.

String[] monday = {"ana", "li", "raj"};
Set<String> notTue = new LinkedHashSet<>(Arrays.asList(monday));
boolean r = notTue.removeAll(Set.of("li", "raj", "tom"));   // true
String diff = notTue.toString();                            // "[ana]"

8.3. How do we compare string arrays ignoring case?

We put the second array into a TreeSet created with String.CASE_INSENSITIVE_ORDER and filter the first array with its contains() method. The result keeps the spelling of the first array.

String[] team = {"ana", "li", "raj"};
Set<String> guests = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
Collections.addAll(guests, "Li", "TOM");
String[] caseless = Arrays.stream(team).filter(guests::contains).toArray(String[]::new);   // [li]

8.4. What is the time complexity of the intersection of two arrays?

With a hash set, it is O(n + m) on average, where n and m are the array lengths. Sorting first and using two pointers costs O(n log n + m log m), and nested loops cost O(n x m).

9. Conclusion

The intersection keeps the values that both arrays contain. For object arrays, a LinkedHashSet with retainAll() gives it in a few lines, as long as the argument is a set and not a list.

For int[], a HashSet of one array and a filtered IntStream over the other is the general solution. A count map keeps repeated matches, the two-pointer loop works on sorted arrays without extra memory, and Collections.disjoint() answers whether there is any common element at all.

10. References

• Collection.retainAll() (Java SE 25 API)
• Collections.disjoint() (Java SE 25 API)
• Map.merge() (Java SE 25 API)
• HashSet (Java SE 25 API)

Happy Learning !!

Source Code on Github