Backend interview prep

Start Learning

Intersection of Two Arrays

Java coding interview problem for Array Coding: Intersection of Two Arrays.

Finding the intersection of two arrays is one of the most common array interview questions.

This problem helps you understand:

  • Hashing
  • Set operations
  • Frequency counting
  • Sorting
  • Two Pointer Technique
  • Array Traversal
  • Time Complexity Optimization

Array intersection concepts are widely used in:

  • Database joins
  • Search systems
  • Recommendation engines
  • Data analytics
  • Permission management systems

What is Array Intersection?

The intersection of two arrays means finding elements that exist in both arrays.

Example:

Array 1:

[1,2,3,4]

Array 2:

[3,4,5,6]

Intersection:

[3,4]

Because:

3 exists in both arrays

4 exists in both arrays

Types of Array Intersection

There are two common interpretations.

1. Unique Intersection

Duplicate values are removed.

Example:

Array 1:

[1,2,2,3]

Array 2:

[2,2,3]

Result:

[2,3]

2. Intersection With Duplicates

Duplicate occurrences are preserved.

Example:

Array 1:

[1,2,2,3]

Array 2:

[2,2,3]

Result:

[2,2,3]

Because:

2 appears twice in both arrays

Why is This Question Asked in Interviews?

Interviewers ask this problem because it tests:

  • Understanding of Sets
  • HashMap usage
  • Sorting techniques
  • Optimization skills
  • Handling duplicates

It is a foundation for advanced problems:

  • Union of Arrays
  • Difference of Arrays
  • Common Elements in Lists
  • Three Sum
  • Four Sum

Real-World Applications

Database JOIN Operations

Finding common records between tables.

Example:

Customers:

[101,102,103,104]

Orders:

[102,103,105]

Common customers:

[102,103]

Social Media

Finding mutual friends.

User A:

[John, Mike, Alex]

User B:

[Mike, Alex, David]

Mutual friends:

[Mike, Alex]

Security Systems

Finding users with common permissions.

System A:

READ, WRITE

System B:

READ, DELETE

Common permission:

READ

Recommendation Systems

Finding common interests between users.

Problem Statement

Given two integer arrays,

find their intersection.

Return unique common elements.

Example 1

Input:

Array 1:

[1,2,2,1]


Array 2:

[2,2]

Output:

[2]

Example 2

Input:

Array 1:

[4,9,5]


Array 2:

[9,4,9,8,4]

Output:

[4,9]

Example 3

Input:

Array 1:

[1,3,5]


Array 2:

[2,4,6]

Output:

[]

Understanding Intersection

Consider:

Array 1:

[10,20,30,40]

Array 2:

[30,40,50,60]

Start:

Result = []

Check Array 1 element:

10

Exists in Array 2?

No

Ignore.

Check:

20

Exists?

No

Ignore.

Check:

30

Exists?

Yes

Add:

[30]

Check:

40

Exists?

Yes

Add:

[30,40]

Final Result:

[30,40]

Mathematical Concept

Intersection is represented as:

A ∩ B

Meaning:

Elements present in:

A

AND

B

Example:

A = {1,2,3}

B = {2,3,4}

Intersection:

A ∩ B = {2,3}

Array Visualization

Input:

Array A

[1,2,3,4,5]


Array B

[3,4,5,6,7]

Common area:

        Common

          ↓

[1,2,3,4,5]

      [3,4,5,6,7]

Result:

[3,4,5]

Dry Run

Input:

A = [5,10,15,20]

B = [10,20,30]

Create Set from B:

{10,20,30}

Traverse A:

Element Exists in Set Action
5 No Ignore
10 Yes Add
15 No Ignore
20 Yes Add

Result:

[10,20]

Approach 1 — Using HashSet (Recommended)

The most common interview solution uses HashSet.

Why?

Because HashSet provides:

  • Fast lookup
  • No duplicate values
  • Average O(1) search

Algorithm

  1. Create a HashSet.
  2. Add all elements from the second array.
  3. Traverse the first array.
  4. Check whether element exists in Set.
  5. Add matching elements to result Set.
  6. Convert result to array.

Java Program

import java.util.*;

public class ArrayIntersectionHashSet {

    public static int[] intersection(
            int[] nums1,
            int[] nums2) {


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


        for (int number : nums2) {

            set.add(number);

        }


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


        for (int number : nums1) {

            if (set.contains(number)) {

                result.add(number);

            }

        }


        return result.stream()
                .mapToInt(Integer::intValue)
                .toArray();

    }


    public static void main(String[] args) {


        int[] nums1 =
                {1,2,2,1};


        int[] nums2 =
                {2,2};


        System.out.println(
                Arrays.toString(
                        intersection(nums1, nums2)));

    }

}

Output

[2]

Step-by-Step Explanation

Create Set:

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

Add second array values:

Input:

[2,2]

Set:

{2}

Duplicates removed automatically.

Traverse first array:

[1,2,2,1]

Check:

1

Not found.

Check:

2

Found.

Add:

{2}

Return:

[2]

Advantages

  • Simple implementation.
  • Fast lookup.
  • Automatically removes duplicates.
  • Works for unsorted arrays.
  • Interview friendly.

Drawbacks

  • Requires extra memory.
  • Hashing overhead.
  • Does not maintain order.

Complexity Analysis

Let:

n = size of first array

m = size of second array

Time:

O(n + m)

Why?

  • Build HashSet → O(m)
  • Traverse first array → O(n)

Space:

O(m)

For storing second array values.

Approach 2 — Using Frequency HashMap

When duplicates matter,

we need to count occurrences.

Example:

Array 1:

[1,2,2,3]

Array 2:

[2,2,3]

Result:

[2,2,3]

HashMap stores:

Value → Count

Example:

2 → 2

3 → 1

Algorithm

  1. Store frequency of first array.
  2. Traverse second array.
  3. If frequency exists:
    • Add element.
    • Decrease count.

Java Program

import java.util.*;

public class ArrayIntersectionFrequency {

    public static int[] intersection(
            int[] nums1,
            int[] nums2) {


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


        for (int number : nums1) {

            frequency.put(
                    number,
                    frequency.getOrDefault(
                            number,0) + 1);

        }


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


        for (int number : nums2) {

            if (frequency.getOrDefault(
                    number,0) > 0) {


                result.add(number);


                frequency.put(
                        number,
                        frequency.get(number)-1);

            }

        }


        return result.stream()
                .mapToInt(Integer::intValue)
                .toArray();

    }

}

Example

Input:

nums1:

[1,2,2,3]


nums2:

[2,2,3]

Frequency:

1 → 1

2 → 2

3 → 1

Process nums2:

2 → Add

2 → Add

3 → Add

Result:

[2,2,3]

Advantages

  • Handles duplicates.
  • Preserves occurrence count.
  • Useful for real-world data.

Drawbacks

  • More complex than HashSet.
  • Requires extra memory.

Complexity Analysis

Time:

O(n + m)

Space:

O(n)

Comparison

Approach Duplicates Time Space
HashSet No O(n+m) O(m)
HashMap Frequency Yes O(n+m) O(n)

Approach 3 — Using Two Pointer Approach (Optimal for Sorted Arrays)

The Two Pointer technique is one of the most efficient ways to find the intersection of two arrays when both arrays are sorted.

Instead of using extra memory like HashSet,

we compare elements directly using two pointers.

Requirement

The arrays must be sorted.

Example:

Sorted Array 1:

[1,2,3,4,5]

Sorted Array 2:

[2,3,4,6,7]

Two Pointer Concept

Use two indexes:

i → Array 1 pointer

j → Array 2 pointer

Compare:

nums1[i]

with

nums2[j]

Case 1

If:

nums1[i] == nums2[j]

Common element found.

Add result.

Move both pointers.

Case 2

If:

nums1[i] < nums2[j]

Move first array pointer.

Why?

Because the smaller value cannot match any future value in second array.

Case 3

If:

nums1[i] > nums2[j]

Move second array pointer.

Visualization

Input:

nums1:

[1,2,3,4,5]


nums2:

[2,3,4,6,7]

Pointers:

 i

[1,2,3,4,5]


    j

[2,3,4,6,7]

Compare:

1 < 2

Move i.

Compare:

2 == 2

Add:

[2]

Move both.

Compare:

3 == 3

Add:

[2,3]

Compare:

4 == 4

Add:

[2,3,4]

Result:

[2,3,4]

Algorithm

  1. Sort both arrays.
  2. Create two pointers.
  3. Compare elements.
  4. Add matching values.
  5. Move pointers accordingly.
  6. Return intersection.

Java Program

import java.util.*;

public class ArrayIntersectionTwoPointer {


    public static int[] intersection(
            int[] nums1,
            int[] nums2) {


        Arrays.sort(nums1);

        Arrays.sort(nums2);


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


        int i = 0;

        int j = 0;


        while (i < nums1.length &&
                j < nums2.length) {


            if (nums1[i] == nums2[j]) {


                if (result.isEmpty() ||
                        result.get(result.size() - 1)
                                != nums1[i]) {


                    result.add(nums1[i]);

                }


                i++;

                j++;


            } else if (nums1[i] < nums2[j]) {


                i++;


            } else {


                j++;

            }

        }


        return result.stream()
                .mapToInt(Integer::intValue)
                .toArray();

    }


    public static void main(String[] args) {


        int[] nums1 =
                {4,9,5};


        int[] nums2 =
                {9,4,9,8,4};


        System.out.println(
                Arrays.toString(
                        intersection(nums1, nums2)));

    }

}

Output

[4,9]

Step-by-Step Explanation

Input:

nums1:

[4,9,5]


nums2:

[9,4,9,8,4]

Sort arrays:

nums1:

[4,5,9]


nums2:

[4,4,8,9,9]

Compare:

4 == 4

Add:

[4]

Compare:

5 < 8

Move nums1 pointer.

Compare:

9 == 9

Add:

[4,9]

Final:

[4,9]

Complexity Analysis

Sorting:

O(n log n + m log m)

Traversal:

O(n + m)

Overall:

O(n log n + m log m)

Space:

O(1)

excluding sorting implementation.

Advantages

  • Memory efficient.
  • No HashMap required.
  • Good for sorted data.
  • Easy to extend for duplicate intersection.

Drawbacks

  • Requires sorting.
  • Sorting modifies original arrays.
  • Slower than HashSet for unsorted arrays.

Approach 4 — Using Java Streams

Java Streams provide a concise functional approach.

The idea:

  1. Convert one array into a Set.
  2. Filter elements from another array.
  3. Remove duplicates.

Java Program

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

public class ArrayIntersectionStreams {


    public static int[] intersection(
            int[] nums1,
            int[] nums2) {


        Set<Integer> set =
                Arrays.stream(nums2)
                        .boxed()
                        .collect(
                          Collectors.toSet());


        return Arrays.stream(nums1)
                .filter(set::contains)
                .distinct()
                .toArray();

    }


    public static void main(String[] args) {


        int[] nums1 =
                {1,2,2,3};


        int[] nums2 =
                {2,3};


        System.out.println(
                Arrays.toString(
                        intersection(nums1, nums2)));

    }

}

Output

[2,3]

Step-by-Step Explanation

Create Set:

nums2

[2,3]

Set:

{2,3}

Stream nums1:

1 → Not found

2 → Found

2 → Found

3 → Found

Apply:

distinct()

Result:

[2,3]

Advantages

  • Clean code.
  • Modern Java style.
  • Easy to read.

Drawbacks

  • Uses additional memory.
  • Stream overhead.
  • Less suitable for learning algorithm fundamentals.

Approach 5 — Sorting + Binary Search

Another approach is:

  1. Sort the second array.
  2. For every element in first array,
  3. Perform binary search.

Algorithm

  1. Sort nums2.
  2. Traverse nums1.
  3. Search current element in nums2.
  4. Add if found.

Java Program

import java.util.*;

public class IntersectionBinarySearch {


    public static int[] intersection(
            int[] nums1,
            int[] nums2) {


        Arrays.sort(nums2);


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


        for (int number : nums1) {


            if (Arrays.binarySearch(
                    nums2,
                    number) >= 0) {


                result.add(number);

            }

        }


        return result.stream()
                .mapToInt(Integer::intValue)
                .toArray();

    }


}

Complexity Analysis

Sorting:

O(m log m)

Binary search for each element:

O(n log m)

Total:

O(m log m + n log m)

Advantages

  • Useful when one array is reused multiple times.
  • Demonstrates binary search.

Drawbacks

  • Slower than HashSet.
  • More complex.
  • Requires sorted data.

Handling Duplicate Elements

Interviewers often ask:

"Should duplicates be included?"

Clarify the requirement.

Unique Intersection

Example:

A:

[1,2,2,3]


B:

[2,2,3]

Output:

[2,3]

Use:

  • HashSet
  • LinkedHashSet
  • Streams distinct()

Intersection With Duplicates

Output:

[2,2,3]

Use:

  • HashMap frequency
  • Two Pointer

Primitive vs Object Arrays

Primitive Array

Example:

int[]

Advantages:

  • Faster
  • Less memory

Object Array

Example:

Integer[]

Advantages:

  • Works with Collections
  • Supports Generics

Comparison of All Approaches

Approach Time Complexity Space Duplicates Best Use Case
HashSet O(n+m) O(m) No General solution
HashMap O(n+m) O(n) Yes Frequency matching
Two Pointer O(n log n + m log m) O(1) Yes Sorted arrays
Streams O(n+m) O(m) No Modern Java
Binary Search O(n log m) O(k) No Repeated searches

Common Interview Mistakes

Mistake 1

Using nested loops.

Example:

for each element

    search second array

Complexity:

O(n*m)

Not optimal.

Mistake 2

Ignoring duplicates.

Always clarify:

Unique intersection?

OR

Intersection with duplicates?

Mistake 3

Assuming HashSet maintains order.

HashSet:

No ordering guarantee

Mistake 4

Sorting without considering modification.

Arrays.sort(nums);

changes the array.

Mistake 5

Not handling empty arrays.

Examples:

[]

[1,2]

Edge Cases

Input Output
[] , [] []
[1,1,1],[1] [1]
[1,2],[3,4] []
Negative numbers Works
Large arrays Choose efficient approach

Interview Follow-up Questions

Q1. Find union of two arrays.

Q2. Find intersection with duplicates.

Q3. Solve without extra space.

Q4. Solve for sorted arrays.

Q5. Find common elements in three arrays.

Q6. How does HashSet work internally?

Q7. Difference between HashSet and HashMap?

Q8. How would you handle millions of records?

Q9. Find common strings instead of integers.

Q10. Implement database JOIN using arrays.

Related Problems

  • Union of Arrays
  • Remove Duplicates
  • Two Sum
  • Three Sum
  • Duplicate Detection
  • Frequency Counting
  • Merge Sorted Arrays
  • Common Characters

Key Takeaways

  • HashSet is the simplest solution for unique intersection.
  • HashMap is required when duplicates matter.
  • Two Pointer is best for sorted arrays.
  • Sorting enables efficient comparison.
  • Choose the approach based on:
    • Input size
    • Ordering requirement
    • Duplicate handling
    • Memory constraints

Frequently Asked Interview Questions

Q1. Which approach is best?

For general unsorted arrays:

HashSet

For sorted arrays:

Two Pointer

Q2. Why use HashSet?

Because lookup is approximately:

O(1)

Q3. Why use two pointers?

Because sorted arrays allow linear traversal without extra memory.

Q4. How are duplicates handled?

Depends on requirement:

  • Unique → Set
  • Multiple occurrences → Frequency Map

Q5. What is the production recommendation?

Choose based on scenario:

  • General data → HashSet
  • Large sorted data → Two Pointer
  • Streaming data → HashMap frequency

Interview Tip

When asked:

"Find intersection of two arrays."

First clarify:

  1. Should duplicates be included?
  2. Are arrays sorted?
  3. Is extra memory allowed?

Then choose:

  1. HashSet → Most common solution
  2. HashMap → Duplicate-aware solution
  3. Two Pointer → Sorted arrays
  4. Streams → Modern Java style

Explaining the trade-offs between these approaches demonstrates strong understanding of Java Collections, algorithms, and production-level problem solving.