Find the First Duplicate Element in a Java Array

How to Find the First Duplicate Element in an Array in Java

This problem hides a subtle but important detail: "find the first duplicate" can have two different meanings depending on how you interpret the word first. Understanding this distinction is essential because each interpretation requires a different algorithm. This guide explains both versions and provides the correct solution for each.

Problem Statement

Given an array like:

{5, 4, 3, 4, 5, 6}

There are two duplicate values:

• 4 appears at indices 1 and 3
• 5 appears at indices 0 and 4

The question is:

Which one is considered the first duplicate?

The answer depends on how "first" is defined.

The Subtle Ambiguity: First Duplicate vs First Repeating Element

Before solving the problem, it's important to understand these two interpretations.

First Duplicate Encountered

This refers to the first value that is detected as a duplicate while scanning the array from left to right.

Example:

{5, 4, 3, 4, 5, 6}

Scanning the array:

• 5 → first occurrence
• 4 → first occurrence
• 3 → first occurrence
• 4 → duplicate found ✅

Result:

4

First Repeating Element (Smallest Original Index)

This refers to the duplicated element whose first occurrence appears earliest in the array.

Using the same array:

{5, 4, 3, 4, 5, 6}

Although 4 is detected first during scanning, 5 first appeared at index 0, which is earlier than 4 at index 1.

Result:

5

Always clarify which interpretation is expected before writing your solution.

Method 1: Single-Pass HashSet (First Duplicate Encountered)

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

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

Set<Integer> seen = new HashSet<>();
int firstDuplicate = -1;

for (int num : numbers) {
    if (!seen.add(num)) {
        firstDuplicate = num;
        break;
    }
}

System.out.println("First duplicate encountered: " + firstDuplicate);

Output:

First duplicate encountered: 4

This solution scans the array once and stops immediately after detecting the first repeated value.

Method 2: Finding the First Repeating Element (Smallest Original Index)

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

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

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

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

int firstRepeatingValue = -1;

for (int num : numbers) {
    if (duplicates.contains(num)) {
        firstRepeatingValue = num;
        break;
    }
}

System.out.println("First repeating element: " + firstRepeatingValue);

Output:

First repeating element: 5

This solution first identifies every duplicate value and then scans the array again to locate the duplicated element whose first occurrence appears earliest.

Step-by-Step Explanation

Method 1: Single-Pass HashSet

Each element is inserted into a HashSet.

If add() returns false, the element has already been seen before.

The algorithm immediately returns that value because it is the first duplicate encountered during the scan.

Method 2: Two-Pass Approach

The first pass identifies every duplicated value.

The second pass scans the original array from the beginning.

The first element encountered that exists in the duplicate set is the duplicated element with the smallest original index.

Internal Working (Memory View)

For the array:

{5, 4, 3, 4, 5, 6}

Method 1

seen = {}

Add 5
seen = {5}

Add 4
seen = {5, 4}

Add 3
seen = {5, 4, 3}

Add 4
Already exists

First duplicate = 4

Method 2

Pass 1

duplicates = {4, 5}

Pass 2

Index 0 -> 5

5 exists in duplicates

First repeating element = 5

Real-Life Analogy

Imagine people joining a queue.

First duplicate encountered means noticing the first person who joins the queue for a second time while watching it happen.

First repeating element means looking back after everyone has joined and asking, "Among everyone who returned, who originally joined the queue first?"

Although similar, these questions have different answers.

Best Practices

• Always clarify what "first duplicate" means before implementing a solution.
• Use the single-pass HashSet solution when the requirement is to find the first duplicate encountered during scanning.
• Use the two-pass solution when the requirement is to find the duplicated element whose first occurrence appears earliest.
• Stop scanning immediately once the required answer is found.

Common Mistakes

1. Assuming both interpretations always produce the same answer.
2. Continuing the scan after finding the required duplicate.
3. Using the single-pass solution when the question actually asks for the first repeating element.
4. Forgetting to handle arrays that contain no duplicates.

Expert Tips

• This ambiguity is a common interview trap. Mentioning both interpretations before coding demonstrates strong problem-analysis skills.
• Both approaches have O(n) time complexity, so correctness matters more than performance when choosing between them.
• The single-pass solution can terminate early, making it slightly more efficient when the first duplicate appears near the beginning of the array.

Comparison Table

Frequently Asked Questions

What is the difference between the first duplicate and the first repeating element?

The first duplicate is the first value detected as a duplicate during scanning, while the first repeating element is the duplicated value whose first occurrence appears earliest in the array.

Which solution should I use during an interview?

First clarify which interpretation the interviewer expects, then choose the appropriate algorithm.

Can both versions be solved in a single pass?

Only the first duplicate encountered can be solved in a single pass. Finding the first repeating element generally requires two passes.

What should I return if the array contains no duplicates?

Return a sentinel value such as -1 or display an appropriate message indicating that no duplicates were found.

Is this the same problem as finding all duplicate elements?

No. This problem asks for only one duplicate based on a positional rule, whereas finding all duplicates returns every repeated value.

Does the order of elements matter?

Yes. Both interpretations depend entirely on the original order of the array.

Can this problem be solved using O(1) extra space?

For sorted arrays, yes. For unsorted arrays without modifying the original data, HashSet-based solutions using O(n) extra space are the standard approach.

How is this different from finding all duplicate elements?

Finding all duplicates returns every repeated value, while this problem asks for only one specific duplicate according to a particular definition of "first."