Backend interview prep

Start Learning

Find Duplicate Elements Using Set

Java coding interview problem for Collections: Find Duplicate Elements Using Set.

Finding duplicate elements is one of the most common problems in Java interviews.

This problem introduces an important data structure concept:

Collection

      ↓

Store Unique Values

      ↓

Detect Repeated Elements

The most commonly used collection for duplicate detection is:

Set

because a Set does not allow duplicate values.

What are Duplicate Elements?

Duplicate elements are values that appear more than once in a collection.

Example:

Input:

[10, 20, 30, 20, 40, 10]

Frequency:

10 → 2 times

20 → 2 times

30 → 1 time

40 → 1 time

Duplicate elements:

10

20

Why Find Duplicate Elements?

Duplicate detection is required in many real-world systems.

Examples:

  • Removing duplicate customer records
  • Detecting duplicate transactions
  • Validating user input
  • Data cleanup
  • Finding repeated logs
  • Duplicate file detection

Understanding Set Data Structure

A Set is a collection that stores:

Unique Elements

Example:

Adding:

10

20

10

Result:

10

20

The second:

10

is ignored.

Java Set Interface

Java provides multiple Set implementations:

Set

 |
 |-- HashSet

 |
 |-- LinkedHashSet

 |
 |-- TreeSet

HashSet

Most commonly used for duplicate detection.

Characteristics:

  • No duplicate elements
  • No insertion order guarantee
  • Fast lookup
  • Uses hashing

Example:

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

Set vs List

Feature List Set
Duplicates Allowed Not Allowed
Order Maintained Depends on implementation
Index Access Yes No
Search O(n) O(1) average
Use Case Ordered data Unique data

Why Set is Used for Duplicate Detection?

The logic is simple:

If an element already exists in Set:

Duplicate Found

Otherwise:

Add Element

Example

Input:

[1,2,3,2]

Start:

Set = {}

Read:

1

Set:

{1}

Read:

2

Set:

{1,2}

Read:

3

Set:

{1,2,3}

Read:

2

Already exists.

Duplicate:

2

HashSet Internal Working

HashSet internally uses:

HashMap

Structure:

HashSet

   |

HashMap

   |

Buckets

   |

Nodes

When adding:

set.add(value);

Java performs:

Value

 ↓

hashCode()

 ↓

Bucket Location

 ↓

equals()

 ↓

Store / Reject

Hash Function Concept

Every object has:

hashCode()

Example:

10

↓

hashCode()

↓

Bucket 5

Collision Handling

Sometimes different values generate the same bucket.

Example:

Value A

    ↓

Bucket 5


Value B

    ↓

Bucket 5

This is called:

Hash Collision

HashSet handles collisions using:

  • Linked structure
  • Tree structure (after threshold)

Real-World Applications

Database Cleanup

Example:

Duplicate customer IDs:

101

102

101

Find:

101

Transaction Processing

Detect:

Duplicate transaction IDs

Security Systems

Detect:

  • Duplicate requests
  • Replay attacks
  • Repeated events

Data Analytics

Find:

  • Repeated values
  • Duplicate patterns

Problem Statement

Given an integer array, find all duplicate elements using Set.

Example 1

Input:

[1,2,3,2,4,1]

Output:

[1,2]

Example 2

Input:

[5,6,7,8]

Output:

[]

No duplicates.

Constraints

Example:

1 <= n <= 100000

Duplicate Detection Visualization

Input:

[10,20,30,20,40,10]

Initial:

Set = {}

Duplicate = []

Read:

10

Add:

Set={10}

Read:

20

Add:

Set={10,20}

Read:

30

Add:

Set={10,20,30}

Read:

20

Already exists.

Duplicate:

[20]

Read:

10

Already exists.

Duplicate:

[20,10]

Approach 1 — Brute Force Comparison

The simplest approach:

Compare every element with every other element.

Algorithm

For every element:

  1. Compare with remaining elements.
  2. If same value found:
  3. Mark as duplicate.

Example

Array:

[10,20,30,20]

Compare:

10 with all

20 with all

30 with all

Find:

20 repeated

Java Program — Brute Force

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

public class DuplicateBruteForce {


    public static List<Integer> findDuplicates(
            int[] numbers) {


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


        for(int i = 0;
            i < numbers.length;
            i++) {


            for(int j = i + 1;
                j < numbers.length;
                j++) {


                if(numbers[i] == numbers[j]
                   &&
                   !duplicates.contains(numbers[i])) {


                    duplicates.add(
                            numbers[i]);

                }

            }

        }


        return duplicates;

    }

}

Dry Run

Input:

[1,2,3,2,1]

Compare:

1 vs 2

1 vs 3

1 vs 2

1 vs 1

Duplicate:

1

Compare:

2 vs 3

2 vs 2

Duplicate:

2

Output:

[1,2]

Complexity Analysis — Brute Force

For:

n elements

Nested loops:

Time:

O(n²)

Space:

O(k)

where:

k = duplicate count

Advantages

  • Easy to understand.
  • No extra data structure required.
  • Good for learning.

Drawbacks

  • Slow for large arrays.
  • Many unnecessary comparisons.
  • Not production friendly.

Approach 2 — Using HashSet

The optimized approach uses:

HashSet

Algorithm

For every element:

  1. Try adding to Set.
  2. If add fails:
  3. Element already exists.
  4. It is duplicate.

Logic

if(!set.add(number)) {

    duplicate found;

}

Java Program — HashSet Approach

import java.util.*;

public class DuplicateUsingSet {


    public static List<Integer> findDuplicates(
            int[] numbers) {


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


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


        for(int number : numbers) {


            if(!set.add(number)) {


                duplicates.add(number);

            }

        }


        return duplicates;

    }


    public static void main(String[] args) {


        int[] numbers =
                {10,20,30,20,40,10};


        System.out.println(
                findDuplicates(numbers));

    }

}

Output

[20,10]

Step-by-Step Explanation

Input:

10,20,30,20,40,10

Start:

Set={}

Duplicates=[]

Add:

10

Set:

{10}

Add:

20

Set:

{10,20}

Add:

30

Set:

{10,20,30}

Add:

20

Already exists.

Duplicate:

20

Add:

10

Already exists.

Duplicate:

10

Final:

[20,10]

Complexity Analysis

For:

n elements

HashSet operations:

Average:

O(1)

Total:

Time:

O(n)

Space:

O(n)

Advantages

  • Fast solution.
  • Simple implementation.
  • Interview preferred.
  • Works for large data.

Drawbacks

  • Uses extra memory.
  • Does not maintain order.

Finding All Duplicate Elements

The previous approach detects duplicates while traversing the array.

A common interview variation is:

Return all duplicate elements without repeating duplicate values.

Example

Input:

[1,2,3,2,4,1,5,2]

Frequency:

1 → 2

2 → 3

3 → 1

4 → 1

5 → 1

Output:

[1,2]

Using Two Sets Approach

We can maintain:

visited elements

+

duplicate elements

Algorithm

  1. Create two sets:
seen

duplicates
  1. Traverse array.
  2. If element exists in seen:
add to duplicates
  1. Otherwise:
add to seen

Java Program — Find All Duplicates

import java.util.*;

public class FindAllDuplicates {


    public static Set<Integer> findDuplicates(
            int[] numbers) {


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


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


        for(int number : numbers) {


            if(!seen.add(number)) {


                duplicates.add(number);

            }

        }


        return duplicates;

    }


    public static void main(String[] args) {


        int[] numbers =
                {1,2,3,2,4,1,5,2};


        System.out.println(
                findDuplicates(numbers));

    }

}

Output

[1,2]

Finding First Duplicate Element

Another common interview question:

Find the first duplicate element in an array.

Example

Input:

[5,3,4,3,5]

Output:

3

Because:

3

is the first element repeated while scanning.

Java Program

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

public class FirstDuplicate {


    public static Integer findFirstDuplicate(
            int[] numbers) {


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


        for(int number : numbers) {


            if(!set.add(number)) {


                return number;

            }

        }


        return null;

    }

}

Dry Run

Input:

[5,3,4,3,5]

Read:

5

Set:

{5}

Read:

3

Set:

{5,3}

Read:

4

Set:

{5,3,4}

Read:

3

Already exists.

Return:

3

Frequency Map Approach

Sometimes interviews ask:

Count duplicate occurrences.

Example:

Input:

[1,2,2,3,3,3]

Output:

1 → 1

2 → 2

3 → 3

Use:

HashMap

Java Program

import java.util.*;

public class DuplicateFrequency {


    public static Map<Integer,Integer> frequency(
            int[] numbers) {


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


        for(int number : numbers) {


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

        }


        return map;

    }

}

Finding Only Duplicate Values From Frequency Map

for(Map.Entry<Integer,Integer> entry :
        map.entrySet()) {


    if(entry.getValue() > 1) {


        System.out.println(
            entry.getKey());

    }

}

LinkedHashSet Approach

A normal HashSet does not guarantee order.

Example:

Input:

[10,20,30,20,10]

HashSet output:

[20,10]

If insertion order is required:

Use:

LinkedHashSet

Example

Set<Integer> duplicates =
        new LinkedHashSet<>();

Output:

[20,10]

in first duplicate discovery order.

LinkedHashSet Internal Structure

LinkedHashSet

       |

HashSet

       |

Linked List

       |

Maintains insertion order

Stream API Approach

Java Streams provide a functional way.

Example:

Input:

[1,2,3,2,4,1]

Stream Solution

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

public class DuplicateUsingStreams {


    public static Set<Integer> findDuplicates(
            List<Integer> numbers) {


        return numbers.stream()

                .collect(
                    Collectors.groupingBy(
                        Function.identity(),
                        Collectors.counting()
                    )
                )

                .entrySet()

                .stream()

                .filter(
                    entry ->
                    entry.getValue() > 1
                )

                .map(
                    Map.Entry::getKey
                )

                .collect(
                    Collectors.toSet()
                );

    }

}

Sorting Based Duplicate Detection

Another approach:

  1. Sort array.
  2. Compare adjacent elements.

Example:

Before:

4 2 1 2 3

After sorting:

1 2 2 3 4

Compare neighbors:

2 == 2

Duplicate.

Java Program

import java.util.*;

public class DuplicateUsingSorting {


    public static List<Integer> findDuplicates(
            int[] numbers) {


        Arrays.sort(numbers);


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


        for(int i = 1;
            i < numbers.length;
            i++) {


            if(numbers[i] ==
               numbers[i-1]) {


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


                    result.add(
                        numbers[i]);

                }

            }

        }


        return result;

    }

}

Complexity Analysis

Sorting approach:

Time:

O(n log n)

Space:

O(1)

if sorting in place.

HashSet vs Sorting Approach

Approach Time Space Use Case
HashSet O(n) O(n) Fast lookup
Sorting O(n log n) O(1) Memory optimization
HashMap O(n) O(n) Need frequency

Duplicate Detection in Custom Objects

For objects:

Example:

Employee

HashSet requires:

equals()

hashCode()

Employee Example

class Employee {


    int id;

    String name;


    @Override
    public boolean equals(
            Object obj) {


        Employee e =
            (Employee)obj;


        return this.id ==
               e.id;

    }


    @Override
    public int hashCode() {


        return id;

    }

}

Now:

Employee(101,"John")

Employee(101,"Bob")

are duplicates.

Because:

id is same

HashSet vs LinkedHashSet vs TreeSet

Feature HashSet LinkedHashSet TreeSet
Duplicates Removed Removed Removed
Order No Insertion Sorted
Performance O(1) O(1) O(log n)
Sorting No No Yes

Primitive vs Object Collections

Primitive:

int[]

works with:

HashSet<Integer>

Example:

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

Java performs:

int

↓

Integer

Autoboxing.

Common Interview Mistakes

Mistake 1

Using List for duplicate detection.

Problem:

contains()

takes:

O(n)

Mistake 2

Not considering order requirements.

Need:

HashSet

or

LinkedHashSet

Mistake 3

Returning repeated duplicates.

Example:

Input:

[1,1,1]

Wrong:

[1,1]

Correct:

[1]

Mistake 4

Ignoring custom object equality.

Need:

equals()

hashCode()

Edge Cases

Case Result
Empty array No duplicates
No duplicates Empty result
All same values Single duplicate
Large array Use HashSet
Objects Override equals/hashCode

Interview Follow-up Questions

Q1. Find duplicate elements using Set.

Q2. Find first duplicate number.

Q3. Find all duplicate numbers.

Q4. Count duplicate frequency.

Q5. Remove duplicates from ArrayList.

Q6. Detect duplicate objects.

Q7. Difference between HashSet and TreeSet.

Related Java Collection Problems

  • Count Word Frequency Using HashMap
  • Remove Duplicate Objects
  • Sort Employees by Salary
  • Two Sum Using HashMap
  • Top K Frequent Elements
  • First Non-Repeating Character

Key Takeaways

Duplicate detection follows a simple pattern:

Read Element

      ↓

Check Existing Value

      ↓

Already Exists?

      ↓

Duplicate Found

Recommended approach:

Fast duplicate detection

HashSet

Need frequency

HashMap

Need sorted duplicates

TreeSet

Complexities:

HashSet:

Time: O(n)

Space: O(n)

Sorting:

Time: O(n log n)

Space: O(1)

Frequently Asked Interview Questions

Q1. Why is Set useful for duplicates?

Because Set stores only unique values.

Q2. How does HashSet detect duplicates?

Using:

hashCode()

+

equals()

Q3. When use HashMap instead of Set?

When frequency/count information is required.

Q4. When use LinkedHashSet?

When insertion order matters.

Interview Tip

When asked:

"Find duplicate elements using Set."

Explain:

  1. Create HashSet.
  2. Traverse input.
  3. Use add().
  4. If add returns false, duplicate exists.
  5. Discuss order and frequency requirements.

For senior Java interviews, mention:

  • HashSet internals.
  • Hash collision handling.
  • Object equality.
  • Alternative sorting approach.

This demonstrates strong understanding of Java Collections and efficient duplicate detection.