Finding the intersection of two lists is a common Java Collections and DSA interview problem.

The problem focuses on finding:

Common Elements

between

Two Collections

Example:

List 1:

[1,2,3,4]

List 2:

[3,4,5,6]

Intersection:

[3,4]

---

What is Intersection of Two Lists?

The intersection of two lists contains elements that exist in both lists.

Mathematically:

A ∩ B

means:

Elements present in A and B

---

Example

List A:

[10,20,30,40]

List B:

[30,40,50,60]

---

Common elements:

30

40

---

Result:

[30,40]

---

Understanding Common Elements

Given:

List A:

1 2 3 4 5


List B:

4 5 6 7 8

---

Compare:

1 → Not present

2 → Not present

3 → Not present

4 → Found

5 → Found

---

Intersection:

4,5

---

Mathematical Set Concept

A set is a collection of unique elements.

Example:

A = {1,2,3,4}

B = {3,4,5,6}

---

Intersection:

A ∩ B

= {3,4}

---

List vs Set Difference

List

Characteristics:

• Allows duplicates.
• Maintains order.
• Supports index access.

Example:

[1,2,2,3]

---

Set

Characteristics:

• Unique values only.
• No duplicate elements.
• Faster lookup.

Example:

{1,2,3}

---

Why Intersection Problems are Asked in Interviews?

This problem tests:

1. Collection Selection

Choosing:

List

or

Set

based on requirements.

---

2. Lookup Optimization

Can you improve:

O(n²)

to

O(n)

?

---

3. Duplicate Handling

Understanding:

• Unique intersection
• Frequency-based intersection

---

4. Data Processing Skills

Used in:

• Database joins
• Search filtering
• Recommendation systems

---

Real-World Applications

Database Operations

SQL:

INNER JOIN

returns common records.

Example:

Customers in:

Product A users

AND

Product B users

---

Social Networks

Find:

Common friends

between two users.

---

Recommendation Systems

Find users who share:

• Interests
• Movies
• Products

---

Data Analytics

Compare:

• Common events
• Shared transactions
• Matching records

---

Problem Statement

Given two lists of integers, find the common elements.

---

Example 1

Input:

List1 = [1,2,3,4]

List2 = [3,4,5,6]

Output:

[3,4]

---

Example 2

Input:

List1 = [10,20,30]

List2 = [30,40,50]

Output:

[30]

---

Example 3 — No Intersection

Input:

[1,2,3]

[4,5,6]

Output:

[]

---

Constraints

Example:

1 <= n <= 100000

---

Intersection Visualization

Input:

List A:

10 20 30 40


List B:

30 40 50 60

---

Convert List A:

Set A:

10

20

30

40

---

Check List B:

30

40

50

60

---

Found:

30

40

---

Approach 1 — Brute Force Comparison

The simplest solution:

For every element in first list:

1. Compare with every element in second list.
2. If matched, add to result.

---

Algorithm

For each element:

List A element

        |

Compare with

        |

All List B elements

---

Example

List A:

[1,2,3]

List B:

[2,3,4]

---

Check:

1 against all

2 against all

3 against all

---

Find:

2,3

---

Java Program — Brute Force

import java.util.*;

public class ListIntersectionBruteForce {


    public static List<Integer> intersection(
            List<Integer> list1,
            List<Integer> list2) {


        List<Integer> result =
                new ArrayList<>();


        for(Integer value : list1) {


            if(list2.contains(value)
                    &&
               !result.contains(value)) {


                result.add(value);

            }

        }


        return result;

    }

}

---

Step-by-Step Explanation

Input:

List1:

[1,2,3,4]


List2:

[3,4,5,6]

---

Read:

1

Check List2:

Not found

---

Read:

2

Check List2:

Not found

---

Read:

3

Found:

Add 3

---

Read:

4

Found:

Add 4

---

Result:

[3,4]

---

Complexity Analysis — Brute Force

Let:

n = size of list1

m = size of list2

---

contains() takes:

O(m)

for ArrayList.

For every element:

n × m

---

Time:

O(n × m)

---

Space:

O(k)

where:

k = intersection size

---

Advantages

• Very easy.
• No additional data structures.
• Good for small lists.

---

Drawbacks

• Slow for large data.
• Repeated searching.
• Not preferred in production.

---

Approach 2 — Using HashSet

The optimized approach uses:

HashSet

because lookup is:

O(1)

average.

---

Algorithm

1. Add first list elements into Set.
2. Traverse second list.
3. Check whether element exists.
4. Add matching elements.

---

Flow

List 1

  ↓

HashSet

  ↓

Check List 2

  ↓

Common Elements

---

Java Program — HashSet Approach

import java.util.*;

public class ListIntersectionHashSet {


    public static List<Integer> intersection(
            List<Integer> list1,
            List<Integer> list2) {


        Set<Integer> set =
                new HashSet<>(
                    list1
                );


        List<Integer> result =
                new ArrayList<>();


        for(Integer value : list2) {


            if(set.contains(value)) {


                result.add(value);

            }

        }


        return result;

    }


    public static void main(String[] args) {


        List<Integer> list1 =
                Arrays.asList(
                    1,2,3,4
                );


        List<Integer> list2 =
                Arrays.asList(
                    3,4,5,6
                );


        System.out.println(
            intersection(
                list1,
                list2
            )
        );

    }

}

---

Output

[3,4]

---

Step-by-Step Explanation

List 1:

[1,2,3,4]

Create Set:

{
1,
2,
3,
4
}

---

Traverse List 2:

3

Exists:

Add

---

4

Exists:

Add

---

5

Not found.

---

6

Not found.

---

Final:

[3,4]

---

Complexity Analysis

Creating HashSet:

O(n)

Checking second list:

O(m)

---

Total:

O(n + m)

---

Space:

O(n)

---

Advantages

• Faster.
• Simple implementation.
• Interview preferred.
• Works well for large lists.

---

Drawbacks

• Extra memory required.
• Does not automatically handle duplicate frequency.

---

Approach 3 — Using Two HashSets

The previous HashSet approach creates one Set and checks the second list.

Another approach is:

Convert both lists into Sets

        ↓

Find common values

        ↓

Return intersection

---

Algorithm

1. Create Set from first list.
2. Create Set from second list.
3. Use:

retainAll()

4. Return remaining elements.

---

Java Program — Two HashSets

import java.util.*;

public class IntersectionUsingTwoSets {


    public static Set<Integer> intersection(
            List<Integer> list1,
            List<Integer> list2) {


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


        Set<Integer> set2 =
                new HashSet<>(list2);


        set1.retainAll(set2);


        return set1;

    }


    public static void main(String[] args) {


        List<Integer> list1 =
                Arrays.asList(
                    1,2,3,4
                );


        List<Integer> list2 =
                Arrays.asList(
                    3,4,5,6
                );


        System.out.println(
            intersection(
                list1,
                list2
            )
        );

    }

}

---

Output

[3,4]

---

Understanding retainAll()

The method:

retainAll()

keeps only elements that exist in both collections.

---

Example:

Set 1:

{1,2,3,4}

Set 2:

{3,4,5,6}

After:

set1.retainAll(set2)

Result:

{3,4}

---

Complexity Analysis

Creating sets:

O(n + m)

retainAll:

O(min(n,m))

---

Overall:

Time:

O(n + m)

Space:

O(n + m)

---

Approach 4 — Java Stream API

Modern Java applications often use Streams.

---

Using filter()

Logic:

Stream List 1

        ↓

Check existence in List 2

        ↓

Collect matches

---

Java Program

import java.util.*;
import java.util.stream.Collectors;


public class IntersectionUsingStreams {


    public static List<Integer> intersection(
            List<Integer> list1,
            List<Integer> list2) {


        return list1.stream()

                .filter(
                    list2::contains
                )

                .distinct()

                .collect(
                    Collectors.toList()
                );

    }

}

---

Example

Input:

List1:

[1,2,3,3,4]


List2:

[3,4,5]

---

Processing:

1 → No

2 → No

3 → Yes

3 → Duplicate

4 → Yes

---

Output:

[3,4]

---

Stream Complexity

Using:

list2.contains()

requires:

O(m)

lookup.

For every element:

O(n × m)

---

Better Stream Solution:

Convert second list into Set.

---

Optimized Stream Approach

public static List<Integer> intersection(
        List<Integer> list1,
        List<Integer> list2) {


    Set<Integer> lookup =
            new HashSet<>(list2);


    return list1.stream()

            .filter(
                lookup::contains
            )

            .distinct()

            .toList();

}

---

Complexity

Creating Set:

O(m)

Stream filtering:

O(n)

---

Total:

O(n + m)

---

Approach 5 — Sorted List Intersection Using Two Pointer

If both lists are already sorted, we can use:

Two Pointer Technique

---

Example:

List 1:

1 2 3 4 5

List 2:

2 4 5 6 7

---

Pointers:

i → List 1

j → List 2

---

Logic

If:

list1[i] == list2[j]

Add result.

Move both.

---

If:

list1[i] < list2[j]

Move:

i++

---

If:

list1[i] > list2[j]

Move:

j++

---

Java Program — Two Pointer

import java.util.*;

public class IntersectionTwoPointer {


    public static List<Integer> intersection(
            List<Integer> list1,
            List<Integer> list2) {


        List<Integer> result =
                new ArrayList<>();


        int i = 0;

        int j = 0;


        while(i < list1.size()
                &&
              j < list2.size()) {


            if(list1.get(i)
                    .equals(list2.get(j))) {


                result.add(
                    list1.get(i)
                );


                i++;

                j++;

            }

            else if(list1.get(i)
                    <
                    list2.get(j)) {


                i++;

            }

            else {


                j++;

            }

        }


        return result;

    }

}

---

Two Pointer Dry Run

Input:

List1:

1 2 3 4


List2:

2 3 5 6

---

Initial:

i=0

j=0

Compare:

1 vs 2

Move i.

---

Compare:

2 vs 2

Match.

Add:

2

Move both.

---

Compare:

3 vs 3

Match.

Add:

3

---

Result:

[2,3]

---

Complexity Analysis

Time:

O(n + m)

Space:

O(1)

excluding result.

---

Handling Duplicate Elements

There are two interpretations.

---

Unique Intersection

Example:

List 1:

[1,2,2,3]

List 2:

[2,2,4]

Result:

[2]

---

Use:

Set

---

Intersection With Frequency

Example:

List 1:

[1,2,2,3]

List 2:

[2,2,2,4]

Result:

[2,2]

---

Need:

HashMap frequency counting

---

Frequency Based Intersection

Algorithm:

1. Count first list frequency.
2. Traverse second list.
3. If frequency exists:
4. Add element.
5. Decrease count.

---

Java Program

import java.util.*;

public class IntersectionWithFrequency {


    public static List<Integer> intersection(
            int[] nums1,
            int[] nums2) {


        Map<Integer,Integer> map =
                new HashMap<>();


        for(int num : nums1) {


            map.put(
                num,
                map.getOrDefault(
                    num,0)+1
            );

        }


        List<Integer> result =
                new ArrayList<>();


        for(int num : nums2) {


            if(map.getOrDefault(
                    num,0) > 0) {


                result.add(num);


                map.put(
                    num,
                    map.get(num)-1
                );

            }

        }


        return result;

    }

}

---

Intersection of Custom Objects

Example:

Employees:

List A:

Employee(101,John)


List B:

Employee(101,John)

Need:

equals()

hashCode()

---

Employee Equality

@Override
public boolean equals(Object obj){

    Employee e =
        (Employee)obj;


    return id == e.id;

}


@Override
public int hashCode(){

    return id;

}

---

Now Set can find common employees.

---

HashSet vs TreeSet

Feature	HashSet	TreeSet
Ordering	No	Sorted
Lookup	O(1)	O(log n)
Duplicates	Removed	Removed
Internal Structure	Hash Table	Red Black Tree

---

Primitive vs Object Collections

Primitive array:

int[]

Collection:

Set<Integer>

---

Java performs:

int

↓

Integer

Autoboxing.

---

Common Interview Mistakes

Mistake 1

Using nested loops.

Complexity:

O(n²)

---

Mistake 2

Ignoring duplicate requirements.

Ask:

Unique intersection?

or

Frequency intersection?

---

Mistake 3

Using HashSet for sorted output.

Use:

TreeSet

---

Mistake 4

Custom objects without equals/hashCode.

Result:

Incorrect intersection.

---

Edge Cases

Case	Result
Empty List	Empty intersection
No common elements	[]
Same lists	All elements
Duplicate values	Depends on requirement
Large data	Use HashSet

---

Interview Follow-up Questions

Q1. Find intersection of two arrays.

Q2. Find unique intersection.

Q3. Find intersection with duplicates.

Q4. Find common elements of objects.

Q5. Difference between retainAll() and filter().

Q6. Implement intersection without extra space.

Q7. Find common elements in sorted arrays.

---

Related Java Collection Problems

• Find Duplicate Elements Using Set
• Remove Duplicate Objects
• Group Employees by Department
• Count Word Frequency Using HashMap
• Two Sum Using HashMap
• Top K Frequent Elements

---

Key Takeaways

Intersection follows this pattern:

Two Collections

        ↓

Find Common Values

        ↓

Return Matching Elements

---

Recommended approaches:

Unsorted Lists

Use:

HashSet

---

Sorted Lists

Use:

Two Pointer

---

Need Duplicate Counts

Use:

HashMap Frequency

---

Complexity:

HashSet:

O(n + m)

Two Pointer:

O(n + m)

---

Frequently Asked Interview Questions

Q1. What is intersection?

Elements common between two collections.

---

Q2. Which data structure is best?

HashSet for unsorted data.

---

Q3. How to preserve duplicates?

Use frequency counting with HashMap.

---

Q4. How to optimize sorted lists?

Use two pointers.

---

Interview Tip

When asked:

"Find intersection of two lists."

Explain:

1. Understand whether duplicates matter.
2. For unsorted lists, use HashSet.
3. For sorted lists, use two pointers.
4. For object lists, implement equals/hashCode.
5. Discuss time and space trade-offs.

For senior Java interviews, discuss:

• Set operations.
• Hashing.
• Stream optimization.
• Frequency maps.
• Database join analogy.

This demonstrates strong understanding of Java Collections and efficient data processing patterns.