Find Duplicate Elements in an Array in Java

How to Find Duplicate Elements in an Array in Java

Finding duplicates in an array is one of the most commonly asked questions in Java interviews because there are several valid approaches with different time and space trade-offs. This guide walks through all of them—from the simple brute-force approach to the efficient HashSet solution that interviewers typically expect.

Problem Statement

Given an array like {4, 2, 7, 4, 9, 2, 8}, the goal is to identify which elements appear more than once.

Output:

4
2

Method 1: Brute Force (Nested Loops)

int[] numbers = {4, 2, 7, 4, 9, 2, 8};

for (int i = 0; i < numbers.length; i++) {
    for (int j = i + 1; j < numbers.length; j++) {
        if (numbers[i] == numbers[j]) {
            System.out.println("Duplicate found: " + numbers[i]);
            break; // Avoid printing the same duplicate multiple times
        }
    }
}

This approach works correctly, but it has O(n²) time complexity because every element is compared with every remaining element. It is mainly useful for understanding the concept or solving very small problems.

Method 2: Using HashSet (Recommended)

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

int[] numbers = {4, 2, 7, 4, 9, 2, 8};

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

for (int num : numbers) {
    if (!seen.add(num)) {
        duplicates.add(num);
    }
}

System.out.println("Duplicates: " + duplicates);

This is the standard interview-preferred solution. It runs in O(n) time with O(n) extra space. The key idea is that Set.add() returns false when the element already exists in the set.

Method 3: Using HashMap for Frequency

import java.util.HashMap;
import java.util.Map;

int[] numbers = {4, 2, 7, 4, 9, 2, 8};

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

for (int num : numbers) {
    frequency.put(num, frequency.getOrDefault(num, 0) + 1);
}

for (Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
    if (entry.getValue() > 1) {
        System.out.println("Duplicate: " + entry.getKey()
                + " (appears " + entry.getValue() + " times)");
    }
}

Unlike the HashSet solution, this method also tells you how many times each duplicate appears while maintaining O(n) time complexity.

Method 4: Sorting-Based Approach

import java.util.Arrays;

int[] numbers = {4, 2, 7, 4, 9, 2, 8};

Arrays.sort(numbers);

for (int i = 1; i < numbers.length; i++) {
    if (numbers[i] == numbers[i - 1]) {
        System.out.println("Duplicate: " + numbers[i]);
    }
}

After sorting the array, duplicate elements become adjacent, making them easy to identify with a single pass. This approach takes O(n log n) time because of sorting while requiring only O(1) extra space when the sort is performed in place.

Method 5: Java Streams

import java.util.Arrays;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

Set<Integer> duplicates = Arrays.stream(numbers)
        .boxed()
        .collect(Collectors.groupingBy(n -> n, Collectors.counting()))
        .entrySet()
        .stream()
        .filter(e -> e.getValue() > 1)
        .map(Map.Entry::getKey)
        .collect(Collectors.toSet());

This modern Java approach uses groupingBy() and counting() to build a frequency map, then filters elements that appear more than once.

Step-by-Step Explanation

HashSet Walkthrough

Two sets are created:

• seen keeps track of every element encountered.
• duplicates stores elements that appear more than once.

Processing Each Element

For every element in the array:

• seen.add(num) attempts to insert the value.
• If add() returns false, the value already exists and is therefore a duplicate.

Recording Duplicates

Whenever a duplicate is found, it is added to the duplicates set. Since it is also a set, duplicate values are stored only once regardless of how many times they appear.

Final Result

After processing the entire array, the duplicates set contains every repeated element exactly once.

Internal Working (Memory View)

HashSet internally uses a hash table. Each element's hash code determines its storage bucket, allowing average-case O(1) insertion and lookup.

Processing the array step by step:

seen = {}

Process 4 → seen = {4}

Process 2 → seen = {4, 2}

Process 7 → seen = {4, 2, 7}

Process 4 → already exists
duplicates = {4}

Process 9 → seen = {4, 2, 7, 9}

Process 2 → already exists
duplicates = {4, 2}

Process 8 → seen = {4, 2, 7, 9, 8}

Final duplicates = {4, 2}

Real-Life Analogy

Imagine checking IDs at the entrance of an event while keeping a list of everyone who has already entered. Every time a new person arrives, you quickly check the list. If their name already exists, you immediately know they are a repeat visitor. You never need to compare every new person with every previous visitor, making the lookup much faster.

Best Practices

• Use the HashSet approach for the standard duplicate-finding problem because it provides O(n) performance.
• Use a HashMap when you also need the frequency of each duplicate.
• Choose the sorting approach only when minimizing extra memory is more important than execution time.
• Avoid the brute-force solution in production code since it does not scale well for large arrays.

Common Mistakes

1. Using nested loops in production code, resulting in O(n²) performance.
2. Forgetting that Set.add() returns a boolean value, making the HashSet solution more complicated than necessary.
3. Printing the same duplicate multiple times instead of displaying each duplicate only once.
4. Confusing the problem of finding duplicates with removing duplicates.

Expert Tips

• The HashSet trick using add() returning false is one of the most common Java interview patterns.
• If memory usage is critical, mention the sorting approach as an alternative because it trades additional time for lower memory consumption.
• If the requirement is to find only the first duplicate, a different approach should be used.

Comparison Table

Frequently Asked Questions

What is the most efficient way to find duplicate elements in a Java array?

The HashSet approach is generally the best choice because it runs in O(n) time while keeping the implementation simple.

Can I find duplicates without using extra data structures?

Yes. Sort the array first and then compare adjacent elements. This requires O(n log n) time and O(1) additional space.

How do I count how many times each duplicate appears?

Use a HashMap<Integer, Integer> to store the frequency of each element, then print entries whose count is greater than one.

Is the brute-force approach ever acceptable?

It is acceptable for learning purposes or very small arrays but should generally be avoided in production because of its O(n²) complexity.

Can Java Streams solve this problem?

Yes. Using Collectors.groupingBy() together with Collectors.counting() allows you to identify duplicate elements in a functional programming style.

Does HashSet preserve the order in which duplicates are found?

No. HashSet does not maintain insertion order. If order matters, use LinkedHashSet.

How is finding duplicates different from finding unique elements?

Finding duplicates identifies values that appear more than once, while finding unique elements identifies values that appear exactly once.

What if the array contains objects instead of primitive values?

The same approaches work as long as the object's class correctly overrides equals() and hashCode(), which HashSet and HashMap rely on internally.