Handling duplicates in arrays is a common problem in programming, often needed for tasks like data validation or optimization. This article explores how to find the index of the first duplicate element in an array using Java. We will cover multiple approaches, from brute-force methods to an optimized solution with Hashset data structure, and demonstrate a functional solution using Java 8+ streams.
1. Problem Statement
Given an array of integers, the task is to find the index of the first duplicate element in the array. A duplicate is defined as an element that appears more than once, and the first duplicate is the one whose second occurrence has the smallest index. If there are no duplicates, return -1.
1.1 Example
Given the array arr = [2, 5, 1, 2, 3, 5, 1, 2, 4], the output is 3 because the first duplicate element is 2, which appears again at index 3.
For the array arr = [3, 1, 4, 5, 6], the output is -1 as there are no duplicate elements in the array.
2. Brute-Force Solution
The brute-force approach compares each element with every other element that appears later in the array. This approach has a time complexity of O(n2).
public class BruteForceDuplicateIndexFinder {
public static int findFirstDuplicateIndexBruteForce(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] == arr[j]) {
return j; // Return the index of the second occurrence
}
}
}
return -1; // No duplicate found
}
public static void main(String[] args) {
int[] arr = {2, 5, 1, 2, 3, 5, 1, 2, 4};
System.out.println("Index of first duplicate: " + findFirstDuplicateIndexBruteForce(arr));
}
}
In the above code snippet, the findFirstDuplicateIndexBruteForce method identifies the index of the first duplicate element in an array using a brute-force approach. It employs two nested loops: the outer loop iterates through each element of the array, while the inner loop compares the current element from the outer loop with all subsequent elements in the array. If a duplicate is found, the method immediately returns the index of the duplicate’s second occurrence. If no duplicates are found after all comparisons, the method returns -1 to indicate that the array contains no duplicates.
Running the above code for the input [2, 5, 1, 2, 3, 5, 1, 2, 4] produces the following output:
Index of first duplicate: 3
3. Optimized Solution Using a Hash Set
To optimize the solution, we can use a HashSet to track the elements we have already seen. The time complexity is O(n), and the space complexity is O(n).
public class OptimizedDuplicateFinderWithSet {
public static int findFirstDuplicateIndex(int[] arr) {
HashSet<Integer> seen = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
if (seen.contains(arr[i])) {
return i; // Found the second occurrence
}
seen.add(arr[i]); // Mark the element as seen
}
return -1; // No duplicate found
}
public static void main(String[] args) {
int[] arr = {2, 5, 1, 2, 3, 5, 1, 2, 4};
System.out.println("Index of first duplicate: " + findFirstDuplicateIndex(arr));
}
}
This approach uses a HashSet to keep track of elements as they are encountered in the array. For each element, it checks whether the element already exists in the set. If it does, the current index is returned as the position of its duplicate. If not, the element is added to the set. If the loop completes without finding any duplicates, the method returns -1.
4. Using Streams (Java 8+)
For a functional programming approach, we can use Java Streams with IntStream and a Set to track duplicates.
public class StreamBasedDuplicateFinder {
public static int findFirstDuplicateIndexWithStreams(int[] arr) {
Set<Integer> seen = new HashSet<>();
return IntStream.range(0, arr.length)
.filter(i -> !seen.add(arr[i]))
.findFirst()
.orElse(-1);
}
public static void main(String[] args) {
int[] arr = {2, 5, 1, 2, 3, 5, 1, 2, 4};
System.out.println("Index of first duplicate: " + findFirstDuplicateIndexWithStreams(arr));
}
}
This approach uses IntStream.range to iterate over the array indices and a Set to track elements. For each element, if it cannot be added to the set because it already exists, its index is captured as the location of the first duplicate. The method returns the index of the first duplicate found or -1 if no duplicates are present.
5. Conclusion
This article explored different methods for finding the index of the first duplicate element in a Java array. We covered a brute-force approach with nested loops, an optimized solution using a HashSet, and a more functional approach with Java 8’s IntStream.
6. Download the Source Code
This article focused on how to find the index of the leftmost duplicate in a Java array.
You can download the full source code of this example here: java array find index leftmost duplicate
