Problem

Given an array of integers, find the first element that repeats (i.e., appears at least twice) and has the smallest index of first occurrence.

Examples

Example 1

1
2
3

Input: [1, 1, 3, 4, 6, 7, 9]
Output: 1
Explanation: 1 is the first element that repeats.

Example 2

1
2
3

Input: [7, 2, 2, 3, 7]
Output: 7
Explanation: 7 is the first element that repeats (appears at index 0 and again at 4).

Example 3

1
2
3

Input: [5, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 3]
Output: 5
Explanation: 5 is the first element that repeats (appears at index 0 and again at 11).

Solution

Method 1 – Brute Force

Intuition

Check each element and see if it appears again later in the array.

Approach

  1. For each element, scan the rest of the array to see if it repeats.
  2. Return the first element that repeats.

Complexity

  • ⏰ Time complexity: O(n²) — Each element may be compared with all others.
  • 🧺 Space complexity: O(1) — No extra space used.

Method 2 – HashSet

Intuition

Track seen elements from right to left, so the last updated index is the smallest index of a repeating element.

Approach

  1. Initialize a variable idx = -1 and an empty set.
  2. Traverse the array from right to left:
  • If the element is not in the set, add it.
  • If it is in the set, update idx to the current index.
  1. After traversal, if idx != -1, return arr[idx]; otherwise, return a suitable message.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  public int firstRepeating(int[] arr) {
    int idx = -1;
    Set<Integer> seen = new HashSet<>();
    for (int i = arr.length - 1; i >= 0; i--) {
      if (seen.contains(arr[i])) {
        idx = i;
      } else {
        seen.add(arr[i]);
      }
    }
    return idx != -1 ? arr[idx] : -1;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
  def first_repeating(self, arr: list[int]) -> int:
    idx = -1
    seen = set()
    for i in range(len(arr) - 1, -1, -1):
      if arr[i] in seen:
        idx = i
      else:
        seen.add(arr[i])
    return arr[idx] if idx != -1 else -1

Complexity

  • ⏰ Time complexity: O(n) — Each element is processed once.
  • 🧺 Space complexity: O(n) — Space for the set.