Find the first repeated element in an array by its index

Objective: Given an array of integers, find out the first repeated element. First repeated element means the element occurs atleast twice and has smallest index.

Input: An Array

Output: The first repeated element

Examples :

Array {1,1,3,4,6,7,9} first repeated Number : 1
Array {7,2,2,3,7} first repeated Number : 7
Array {5,3,3,3,3,3,3,3,4,4,4,5,3} first repeated Number : 5


Naive Solution :

Use two for loops. Time Complexity O(N2).

Better Solution: Using HastSet, Time Complexity O(N).

  • Take a variable say index = -1.
  • Initialize a HashSet.
  • Navigate the array from right to left(backwards) taking one element at a time
  • if HashSet doesnt contain element, add it
  • if HashSet contains then update the index with current index in navigation.
  • At the end index will be updated by the element which is repeated and has the lowest index.

Complete Code:


first repeated element by index is : 2

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

%d bloggers like this: