Partner – Moderne – NPI EA (cat=Spring Boot)
announcement - icon

Refactor Java code safely — and automatically — with OpenRewrite.

Refactoring big codebases by hand is slow, risky, and easy to put off. That’s where OpenRewrite comes in. The open-source framework for large-scale, automated code transformations helps teams modernize safely and consistently.

Each month, the creators and maintainers of OpenRewrite at Moderne run live, hands-on training sessions — one for newcomers and one for experienced users. You’ll see how recipes work, how to apply them across projects, and how to modernize code with confidence.

Join the next session, bring your questions, and learn how to automate the kind of work that usually eats your sprint time.

Course – Black Friday 2026 – NPI EA – main – before_post_content
announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

Course – Black Friday 2026 – NPI – main – before_post_content
announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

1. Overview

Finding the index of the first duplicate element in an array is a common coding problem that can be approached in various ways. While the brute-force method is straightforward, it can be inefficient, especially for large datasets.

In this tutorial, we’ll explore different approaches to solve this problem, ranging from a basic brute-force solution to more optimized techniques using data structures like HashSet and array indexing.

2. Problem Statement

Given an array of integers, we want to find the index of the first duplicate element in an array.

Input: arr = [2, 1, 3, 5, 3, 2]
Output: 4
Explanation: the first element that repeats is 3, and its second occurrence is at index 4. So the correct answer is 4.

Input: arr = [1, 2, 3, 4, 5]
Output: -1
Explanation: Since no elements repeat, the correct answer is -1.

3. Brute Force Approach

In this approach, we check each element of the array and compare it with all subsequent elements to find the first duplicate.

Let’s first look at the implementation and then understand it step by step:

int firstDuplicateBruteForce(int[] arr) {
    int minIndex = arr.length;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] == arr[j]) {
                minIndex = Math.min(minIndex, j);
                break;
            }
        }
    }
    return minIndex == arr.length ? -1 : minIndex;
}

Let’s review this code:

  • We loop over every element i, and for each element, we look for its duplicate at a later index j.
  • When we find a duplicate, we compare j (the index of the second occurrence) with minIndex, which tracks the earliest second occurrence of any duplicate.
  • The break ensures we only track the first-second occurrence of a duplicate for each element.
  • In the end, if minIndex hasn’t been updated, it means there were no duplicates, so we return -1.

Now, let’s discuss the time and space complexity. We use two nested loops, each iterating over the array, leading to a quadratic time complexity. So, the time complexity is O(n^2). Since the extra space we used is independent of the size of the input, the space complexity is O(1).

4. Using HashSet

We can use a HashSet to store the elements we’ve seen so far. As we iterate through the array, we check if an element has already been seen. If so, we return its index as the first duplicate.

Let’s first look at the implementation and then understand it step by step:

int firstDuplicateHashSet(int[] arr) {
    HashSet<Integer> firstDuplicateSet = new HashSet<>();
    for (int i = 0; i < arr.length; i++) {
        if (firstDuplicateSet.contains(arr[i])) {
            return i;
        }
        firstDuplicateSet.add(arr[i]);
    }
    return -1;
}

Let’s review this code:

  • Create an empty HashSet.
  • Loop through the array.
  • For each element, check if it exists in the HashSet.
    • If it does, return the index (first duplicate).
    • If it doesn’t, add the element to the set.
  • If no duplicate is found, return -1.

We’ll now consider the example we mentioned at the start and have a dry run:

First Duplicate Hashset

If we look at time and space complexity, we iterate through the array once, and checking/inserting elements in a HashSet is O(1) on average, so the time complexity is O(n). In the worst case, we may need to store all elements in the HashSet, so the space complexity is O(n).

5. Using Array Indexing

If the elements are positive and within a specific range, i.e., between 1 and n for an array of size n, we can avoid using extra space by modifying the array itself. This approach works under the assumption that all elements are positive and within the range [1, n].

Let’s first look at the implementation and then understand it step by step:

int firstDuplicateArrayIndexing(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int val = Math.abs(arr[i]) - 1;
        if (arr[val] < 0) {
            return i;
        }
        arr[val] = -arr[val];
    }
    return -1;
}

Let’s review this code:

  • Iterate through the array.
  • For each element, treat the value as an index and mark the corresponding element negative.
  • If we encounter a negative value at the calculated index, it means the element has already been encountered, and we return the current index as the first duplicate.
  • If no duplicates are found, return -1.

We’ll now consider the example we mentioned at the start and have a dry run:

First Duplicate Array Indexing

Now, let’s discuss the time and space complexity. Since we iterate through the array once, the time complexity will be O(n), and as we used no extra space, the space complexity will be O(1).

6. Conclusion

In this article, we saw that identifying the first duplicate in an array can be done using different strategies, each with its time and space complexity trade-offs.

The brute-force approach, while simple, isn’t ideal for larger datasets due to its O(n^2) time complexity. Optimized approaches provide significant performance improvements, such as using a HashSet or modifying the array.

Choosing the right solution depends on the problem constraints, such as whether extra space is allowed or if the array can be modified. Understanding these techniques equips us with versatile tools for tackling similar problems efficiently.

The code backing this article is available on GitHub. Once you're logged in as a Baeldung Pro Member, start learning and coding on the project.
Partner – Moderne – NPI EA (tag=Refactoring)
announcement - icon

Modern Java teams move fast — but codebases don’t always keep up. Frameworks change, dependencies drift, and tech debt builds until it starts to drag on delivery. OpenRewrite was built to fix that: an open-source refactoring engine that automates repetitive code changes while keeping developer intent intact.

The monthly training series, led by the creators and maintainers of OpenRewrite at Moderne, walks through real-world migrations and modernization patterns. Whether you’re new to recipes or ready to write your own, you’ll learn practical ways to refactor safely and at scale.

If you’ve ever wished refactoring felt as natural — and as fast — as writing code, this is a good place to start.

Course – Black Friday 2026 – NPI EA – main – after_post_content

announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

Course – Black Friday 2026 – NPI – main – after_post_content

announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW