> For the complete documentation index, see [llms.txt](https://abhyas-kanaujia.gitbook.io/lb-dsa-notes-and-homework-abhyas/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://abhyas-kanaujia.gitbook.io/lb-dsa-notes-and-homework-abhyas/08-array-problems-ii/discord-homework-list/02-first-repeating-element.md).
# 02 First Repeating Element
{% embed url="" %}
Question
Given an array `arr[]` of size `n`, find the first repeating element. The element should occur more than once and the index of its first occurrence should be the smallest.
### **Example 1**
```
Input:
n = 7
arr[] = {1, 5, 3, 4, 3, 5, 6}
Output: 2
Explanation:
5 is appearing twice and
its first appearence is at index 2
which is less than 3 whose first
occuring index is 3.
```
### **Example 2**
```
Input:
n = 4
arr[] = {1, 2, 3, 4}
Output: -1
Explanation:
All elements appear only once so
the answer is -1.
```
The function `firstRepeated()` takes `arr` and `n` as input parameters and returns the position of the first repeating element. If there is no such element -1 is returned.\
1-based indexing is used.
**Expected Time Complexity:** $$O(n)$$
**Expected Auxilliary Space:** $$O(n)$$
### **Constraints**
$$1 \le n \le 10^6$$
$$0 \le A\_i \le 10^6$$
### Naive Approach
Logic
1. Run two nested loops
2. For every element from the outer loop
1. Check all the elements after that element
1. If the same element is found then return the iterator of the outer loop
3. If still nothing found then return -1
Code
```c
int firstRepeated(int arr[], int n) {
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
if(arr[i] == arr[j])
return i + 1;
return -1;
}
```
Complexity
Time Complexity: $$O(n^2)$$
Space Complexity: $$O(1)$$
### Using map
Logic
1. `firstRepeating = -1` stores the index of the first repeating element.
2. We traverse the array from right to left.
3. A set `visited` will store those elements that we have encountered on the right side of the current element.
4. While traversing from right to left
1. If any element has already been visited
1. It is a repeating element.
1. Suppose this is the first occurence of the repeating element.
1. Update `firstRepeating`
2. Otherwise add it to the visited list
5. In the end, either we have `-1` in `firstRepeating` which tells that there are no repetitive elements, or we find the index of the repeating element.
Code
```cpp
int firstRepeated(int arr[], int n) {
int firstRepeating = -1;
unordered_set visited;
for(int i = n - 1; i >= 0; i--) {
if(visited.count(arr[i]))
firstRepeating = i;
visited.insert(arr[i]);
}
return ((firstRepeating == -1) ? -1 : firstRepeating + 1);
}
```
Complexity
Time Complexity: $$O(n)$$
Space Complexity: $$O(n)$$
### Using set
```cpp
int firstRepeated(int arr[], int n) {
int firstRepeating = -1;
unordered_set visited;
for(int i = n - 1; i >= 0; i--) {
if(visited.count(arr[i]))
firstRepeating = i;
visited.insert(arr[i]);
}
return ((firstRepeating == -1) ? -1 : firstRepeating + 1);
}
```
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://abhyas-kanaujia.gitbook.io/lb-dsa-notes-and-homework-abhyas/08-array-problems-ii/discord-homework-list/02-first-repeating-element.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.