Find the First Repeating Element in an Array

Title: Find the First Repeating Element in an Array

In this guide, you will learn how to find the first repeating element in an array using Java. The problem looks deceptively simple, but the “first” in the question is doing a lot of work. We are not asked for any repeating element, and we are not asked for the duplicate that appears earliest when scanning left to right – we are asked for the element whose first occurrence has the smallest index among all values that repeat.

Let us explore a clean O(n) solution that uses a HashSet and a right-to-left scan. We will walk through the algorithm, trace it on a small input, cover the edge cases, and finish with the follow-up questions a Java interviewer is likely to ask once you solve the base problem.

Understanding the Problem

Given an integer array numbers, return the index of the first repeating element. An element is “repeating” if it appears at least twice in the array. The “first repeating element” is the one whose first occurrence has the smallest index among all repeating values.

For example, in {10, 5, 3, 4, 3, 5, 6} both 5 and 3 repeat. The first occurrence of 5 is at index 1 and the first occurrence of 3 is at index 2, so the first repeating element is 5, returned at index 1. If no element repeats, we return -1 to signal the absence of a result.

Approach / Algorithm Steps

The key insight is to scan the array from right to left while tracking which values we have already seen. Every time we revisit a value, the current index is a candidate for the answer, and because we move leftward the last candidate we assign is the smallest index.

1. Validate the input. If numbers is null or has fewer than two elements, return -1 immediately.
2. Create an empty HashSet<Integer> called seen and an integer firstIndex initialized to -1.
3. Iterate i from numbers.length - 1 down to 0.
4. If numbers[i] is already in seen, update firstIndex to i. The element at this index has a duplicate somewhere to its right.
5. Otherwise, add numbers[i] to seen so later (leftward) iterations can detect it.
6. After the loop ends, firstIndex holds either the smallest index whose element repeats or -1 if no element repeated.
7. Return firstIndex.

Java Program

The following complete program defines the method findFirstRepeating and a main that demonstrates it on a sample array.

import java.util.HashSet;

public class FirstRepeatingElement {
    public static int findFirstRepeating(int[] numbers) {
        if (numbers == null || numbers.length < 2) {
            return -1;
        }
        HashSet<Integer> seen = new HashSet<>();
        int firstIndex = -1;
        for (int i = numbers.length - 1; i >= 0; i--) {
            if (seen.contains(numbers[i])) {
                firstIndex = i;
            } else {
                seen.add(numbers[i]);
            }
        }
        return firstIndex;
    }

    public static void main(String[] args) {
        int[] numbers = {10, 5, 3, 4, 3, 5, 6};
        int index = findFirstRepeating(numbers);
        if (index == -1) {
            System.out.println("No repeating element found");
        } else {
            System.out.println("First repeating element: " + numbers[index] + " at index " + index);
        }
    }
}

Explanation of the Program

The method findFirstRepeating accepts an integer array and returns the index of the first repeating element, or -1 when no element repeats. The first if short-circuits two trivial cases, a null reference and any array with zero or one element, because at least two slots are needed for a repeat to exist.

Inside the method we create a HashSet<Integer> named seen and an int accumulator firstIndex initialized to -1. The loop runs backwards: i starts at numbers.length - 1 and decrements to 0. At every step we ask whether numbers[i] has already appeared in a previous (that is, rightward) iteration by calling seen.contains.

When the set already contains the current value, we overwrite firstIndex with i. Each overwrite shifts the recorded index further left, so by the time the loop terminates firstIndex holds the leftmost index whose value also appears somewhere to its right. If the current value is new to the set, we add it so later iterations can detect it. The main method wires everything up on the sample array {10, 5, 3, 4, 3, 5, 6} and prints either the located element or a not-found message.

Step-by-Step Trace

Let us trace the algorithm on the input {4, 6, 9, 2, 6, 4}, where the expected first repeating element is 4 at index 0.

At the end of each iteration, firstIndex holds the smallest index in numbers[i..length-1] whose value appears more than once in that same suffix. When the loop finishes, that suffix is the entire array, which is exactly the answer we want.

Examples

Example 1: No Repeating Element

When every element is unique, the loop never finds a value in seen and firstIndex stays at its initial -1.

int[] input = {1, 2, 3, 4, 5};
// No repeating element found

Example 2: All Identical Elements

When every element is the same value, the algorithm still returns index 0, because that is the leftmost position whose value appears later in the array.

int[] input = {7, 7, 7, 7};
// First repeating element: 7 at index 0

Example 3: Mixed Repeats

When multiple values repeat, the answer is the one whose first occurrence lies earliest, not the one that duplicates earliest when scanning left to right.

int[] input = {8, 1, 4, 1, 8, 4};
// First repeating element: 8 at index 0

Common Mistakes to Avoid

The problem has a very specific definition of “first”, and most incorrect solutions fail because they answer a slightly different question.

• Returning the second occurrence – scanning left to right with a HashSet and returning on the first match gives the earliest duplicate, not the first repeating element. On {10, 5, 3, 4, 3, 5, 6} this returns index 4 instead of index 1. Scan right to left and track the leftmost repeat index, or scan left to right and keep updating until the loop ends.
• Breaking out of the loop early – exiting on the first match from the right-to-left scan returns the rightmost repeat it hits, which is the wrong direction. Let the loop run to completion so firstIndex keeps shifting left.
• Comparing values instead of indices – returning numbers[firstIndex] when the problem asks for the index, or returning the index when it asks for the value, is a common slip. Read the required return type carefully and stick to it.
• Using a List for membership checks – calling list.contains inside a loop is O(n) per call, which turns the whole algorithm into O(n^2). Use a HashSet for O(1) average-case lookups.
• Autoboxing in a hot loop – storing int values in a HashSet<Integer> is fine for correctness, but it allocates an Integer per insertion. For very large arrays, swap to a primitive int hash set from a library like Eclipse Collections to cut allocations.

Edge Cases to Test

Walk through these shapes before claiming the solution works end to end.

• Empty array
• Single-element array
• Array with no repeats
• Array where every element is identical
• Repeat only at the two ends (first and last positions)
• Multiple distinct values that each repeat
• Negative numbers mixed with positive numbers
• Integer.MIN_VALUE or Integer.MAX_VALUE as a repeated value
• Null array reference

Additional Considerations

The time complexity is O(n), where n is the length of numbers. Every element is visited exactly once, and each HashSet operation is O(1) on average. The space complexity is O(n) in the worst case, because when all values are distinct the set grows to the size of the array.

The right-to-left direction is a deliberate design choice. Scanning left to right with a set lets us detect duplicates easily, but it gives the index of the second occurrence first. Scanning right to left means that whenever we see a value we have already recorded, the current (leftward) index is a better answer than any previously recorded one, so we overwrite freely. The last overwrite wins, and the last overwrite is always the smallest index.

Using Integer.MIN_VALUE or Integer.MAX_VALUE as a value causes no problems because HashSet<Integer> hashes the boxed Integer, not a derived numeric offset. There is no risk of overflow in the comparisons, since we never arithmetically combine array values.

Interview Follow-up Questions

Once you solve the base problem, expect the interviewer to prod at these variations to probe how well you understand the invariant.

• What if you must return the first repeating element without using extra space? – if values are bounded by n, mark visited indices by negating numbers[Math.abs(numbers[i])] and track the leftmost index whose target slot is already negative.
• What if the input is read-only, so negation is not allowed? – sort a copy with its original indices attached, group adjacent equal values, and pick the group with the smallest original first index. This trades O(n) extra memory for O(n log n) time.
• What if the array is streamed and does not fit in memory? – approximate membership with a Bloom filter, then confirm candidates against a bounded on-disk index. You trade exactness for a tunable false-positive rate.
• What if duplicate detection must be concurrent across threads? – replace HashSet with ConcurrentHashMap.newKeySet() and use an AtomicInteger for firstIndex, updating it with accumulateAndGet(i, Math::min) only when a membership check succeeds.
• What if we need every repeating element in order of first occurrence, not just the first? – keep a LinkedHashMap from value to its first index, build it in one forward pass, then emit entries whose value appears again later.

Conclusion

Finding the first repeating element is a small problem that tests whether you can read a specification carefully. The right-to-left HashSet scan gives you an O(n) solution that is easy to defend at a whiteboard and easy to extend when the interviewer tightens the constraints.

Try adapting the code to return the value instead of the index, or to handle a List<Integer> input, and the invariant will stay the same. You can learn more about array problems like this one on our Arrays category page: Arrays.