Find Intersection of Arrays in Java
Problem
The intersection of two arrays is every element that appears in both of them, regardless of how many times it appears in either one.
Given two arrays, find every element that appears in both.
Java Program
import java.util.HashSet;
import java.util.Set;
public class IntersectionOfArrays {
public static void main(String[] args) {
int[] arr1 = {3, 6, 9, 12, 15};
int[] arr2 = {6, 12, 18, 24};
Set<Integer> inSecond = new HashSet<>();
for (int num : arr2) {
inSecond.add(num); // mark every value present in arr2
}
Set<Integer> printed = new HashSet<>();
StringBuilder result = new StringBuilder();
for (int num : arr1) {
if (inSecond.contains(num) && !printed.contains(num)) { // shared, and not already listed
if (result.length() > 0) result.append(", ");
result.append(num);
printed.add(num);
}
}
System.out.println("Intersection: " + result);
}
}Output
Core Logic
Marking which values appear anywhere in the second array, then scanning the first array in order, finds every value both arrays share.
- 1A
HashSet<Integer>namedinSecondholds every distinct value found inarr2. - 2A second
HashSet<Integer>namedprintedtracks which common values have already been added to the result, avoiding duplicates. - 3The scan walks
arr1in order; a value is added to the result only if it's present ininSecondand not yet inprinted. - 4Adding a value to the result also marks it in
printed, so a repeated value inarr1isn't listed twice.
[3, 6, 9, 12, 15] and [6, 12, 18, 24], the values 6 and 12 appear in both arrays, so they're reported in the order they first appear in arr1.Key Point: The result order follows arr1's first-appearance order, not arr2's — swapping which array is scanned would list the same values in a different order.
Why: Both arrays are scanned once each, and the sets backing the lookups can hold up to n and m distinct elements respectively.
Key Concepts
Approach 2: Java 8
import java.util.Arrays;
import java.util.Set;
import java.util.stream.Collectors;
public class IntersectionOfArraysStream {
public static void main(String[] args) {
int[] arr1 = {3, 6, 9, 12, 15};
int[] arr2 = {6, 12, 18, 24};
Set<Integer> secondSet = Arrays.stream(arr2).boxed()
.collect(Collectors.toSet());
// Keeps only arr1's distinct elements that also appear in arr2's set
String result = Arrays.stream(arr1).boxed()
.distinct()
.filter(secondSet::contains)
.map(String::valueOf)
.collect(Collectors.joining(", "));
System.out.println("Intersection: " + result);
}
}
Output
Core Logic
Building a Set of the second array's elements lets a stream over the first array keep only the ones present in both, in one filtered pass.
- 1
Arrays.stream(arr2).boxed().collect(Collectors.toSet())builds aSet<Integer>of every distinct element inarr2. - 2
Arrays.stream(arr1).boxed().distinct()turnsarr1into a stream of its own distinct elements, in first-appearance order. - 3
.filter(secondSet::contains)keeps only the elements that also appear inarr2's set. - 4
.collect(...)joins the surviving elements into the final result.
arr1's distinct elements against the set built from arr2 keeps 6 and 12, matching the manual version.Key Point: .distinct() on arr1's stream does the same job as the manual version's printed set — both exist to stop a repeated value in arr1 from being listed twice.
Why: Both scans still run in time proportional to the input arrays, and the set backing the lookups can hold up to m distinct elements from arr2.