Find the Intersection of Two Arrays - Java

Category: Medium | Concepts used: HashSet-based lookup, two-pointer on sorted arrays

---

Problem Statement

Given two arrays, find the elements that appear in both (the intersection).

Input : [1,2,2,3], [2,2,4]      Output: [2] or [2,2] — depends on whether duplicates should be counted!

Note: Two common interpretations: (1) Set intersection — each common value appears once, regardless of how many times it repeats in either array. (2) Multiset intersection — a value appears min(count in A, count in B) times. Always clarify which one is wanted.

Examples (with edge scenarios)

#	Array A	Array B	Set Intersection	Multiset Intersection	Why
1	[1,2,2,3]	[2,2,4]	[2]	[2,2]	2 appears twice in both — multiset keeps both
2	[]	[1,2]	[]	[]	Nothing in common with an empty array
3	[1,2,3]	[4,5,6]	[]	[]	No overlap at all
4	[1,1,1]	[1]	[1]	[1]	Multiset takes min(3,1)=1 occurrence
5	[1,2,3]	[3,2,1]	[1,2,3] (any order)	[1,2,3]	Fully overlapping sets, order in output usually doesn’t matter

Common Fresher Mistake

Mistake	What happens	Fix
Not clarifying set vs. multiset intersection before coding	Might solve the “wrong version” of the problem	Always ask: “should common values appear once, or as many times as they overlap?”
Using nested loops to compare every element of A against every element of B	Works, but O(n*m) — slow for large arrays	Use a HashSet for O(n+m) lookup instead

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether the array may be null or empty, whether duplicates and original order matter, whether the method may modify the input, and whether the answer should contain values or original indices. These choices can change both the code and the best data structure.

Analogy: Warehouse Inventory Comparison

Imagine you are comparing the inventory of two warehouses, A and B:

• Set Intersection (Solution 1 - Presence Check): You look at Warehouse B’s items. For every item (like “Screw Type X”), you check if Warehouse A has at least one screw of this type. If yes, you write “Screw Type X” on your clipboard. If you see more screws of the same type in B, you don’t repeat the label on your clipboard because you already noted its presence.
• Multiset Intersection (Solution 2 - Count Matching): You write down the exact quantities of Warehouse A’s items: 2 boxes of Screws.
  • As you inspect Warehouse B, you see a box of Screws. Since A has matching boxes left, you add one box to the shipment list (result.add(num)) and cross out one box from A’s list (freqA.put(num, count - 1)).
  • You see a second box of Screws in B. You check A’s list again. Since A still has 1 box left, you add a second box to the shipment list and cross out A’s remaining box.
  • You see a third box of Screws in B. You check A’s list. A is out of boxes (count = 0), so you skip it.
  • The shipment list ends up with exactly 2 boxes, matching the intersection quantity!

---

Solution 1 — Using HashSet (Set Intersection — Each Common Value Once)

Intuition

Put all of array A’s values into a Set (for fast lookup). Then, for each value in array B, simply ask “is this in A’s set?” — if yes, it’s part of the intersection. Using a Set for the result too automatically avoids adding the same common value more than once.

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

public class ArrayIntersectionSet {
    public static Set<Integer> intersection(int[] a, int[] b) {
        Set<Integer> setA = new HashSet<>();
        for (int num : a) {
            setA.add(num);
        }

Set<Integer> result = new HashSet<>();
        for (int num : b) {
            if (setA.contains(num)) {
                result.add(num); // Set automatically avoids duplicates in the result too
            }
        }
        return result;
    }

public static void main(String[] args) {
        System.out.println(intersection(new int[]{1,2,2,3}, new int[]{2,2,4})); // [2]
        System.out.println(intersection(new int[]{1,2,3}, new int[]{4,5,6}));    // []
    }
}

Output:

[2]
[]

Dry Run (a=[1,2,2,3], b=[2,2,4])

setA = {1, 2, 3}   (duplicates auto-collapsed when building the set)

b[0]=2 -> setA.contains(2)? yes -> result={2}
b[1]=2 -> setA.contains(2)? yes -> result={2} (already there, Set ignores re-add)
b[2]=4 -> setA.contains(4)? no -> skip

Final: {2}

Interviewer’s take

This is the standard answer for set intersection — O(n+m) time, clean logic using well-known collection types. Make sure to state clearly that this treats intersection as a set operation (no duplicate counting).

Follow-up questions you might get:

• “What if duplicates should be preserved based on their overlap count?” → leads to Solution 2.

---

Solution 2 — Using Frequency Maps (Multiset Intersection — Preserves Overlap Count)

Intuition

Instead of just checking “is it present,” count how many times each value appears in A. Then, walk through B: for each value, if A still has a remaining count for it (greater than 0), include it in the result and decrement A’s count for that value — this ensures we never “reuse” more copies of a value than actually existed in A.

import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;

public class ArrayIntersectionMultiset {
    public static List<Integer> intersection(int[] a, int[] b) {
        HashMap<Integer, Integer> freqA = new HashMap<>();
        for (int num : a) {
            freqA.put(num, freqA.getOrDefault(num, 0) + 1);
        }

List<Integer> result = new ArrayList<>();
        for (int num : b) {
            int count = freqA.getOrDefault(num, 0);
            if (count > 0) {
                result.add(num);
                freqA.put(num, count - 1); // "use up" one occurrence from A
            }
        }
        return result;
    }

public static void main(String[] args) {
        System.out.println(intersection(new int[]{1,2,2,3}, new int[]{2,2,4})); // [2, 2]
        System.out.println(intersection(new int[]{1,1,1}, new int[]{1}));         // [1]
    }
}

Output:

[2, 2]
[1]

Dry Run (a=[1,2,2,3], b=[2,2,4])

freqA = {1:1, 2:2, 3:1}

b[0]=2 -> freqA.get(2)=2 > 0 -> add 2 to result, freqA[2]=1 -> result=[2]
b[1]=2 -> freqA.get(2)=1 > 0 -> add 2 to result, freqA[2]=0 -> result=[2,2]
b[2]=4 -> freqA.get(4)=0 -> skip

Final: [2, 2]  (both overlapping copies of 2 correctly preserved)

Interviewer’s take

This is the correct answer for multiset intersection, and it’s the version most interviewers actually expect by default when they say “find the intersection” without further clarification (it matches how intersection works for things like inventory counts — e.g., “how many of each item do both warehouses have in common”). The decrement trick (count - 1) is the key detail that ensures correctness.

---

📊 Visual Flowchart

graph TD
    Start["Input: Arrays A and B"] --> Method{"Intersection Type?"}
    Method -->|Set Intersection| SetApproach["Build setA from A<br>Initialize resultSet"]
    SetApproach --> LoopSet{"For each num in B"}
    LoopSet -->|Contains| AddSet["resultSet.add(num)"]
    LoopSet -->|Does not contain| SkipSet["Skip"]
    AddSet --> LoopSet
    SkipSet --> LoopSet
    Method -->|Multiset Intersection| MultisetApproach["Build freqMap from A<br>Initialize resultList"]
    MultisetApproach --> LoopMulti{"For each num in B"}
    LoopMulti --> CheckCount{"freqMap[num] > 0?"}
    CheckCount -->|Yes| AddMulti["resultList.add(num)<br>freqMap[num]--"]
    CheckCount -->|No| SkipMulti["Skip"]
    AddMulti --> LoopMulti
    SkipMulti --> LoopMulti

---

Final Verdict — Which Solution Should You Give?

• Always clarify set vs. multiset intersection first — this single question often matters more to the interviewer than which code you write.
• Solution 1 (HashSet) if duplicates shouldn’t be repeated in the output.
• Solution 2 (frequency map) if overlapping counts should be preserved — this is the more commonly expected default interpretation.

---

Quick Recap

Approach	Handles duplicates correctly (multiset)?	Time	Space
HashSet	No — collapses to unique values	O(n+m)	O(n+m)
Frequency map with decrement	Yes	O(n+m)	O(n+m)