Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find the first repeated element in an array by its index

Objec­tive: Given an array of inte­gers, find out the first repeated ele­ment. First repeated ele­ment means the ele­ment occurs atleast twice and has small­est index.

Input: An Array

Out­put: The first repeated element

Exam­ples :

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

Approach:

Naive Solu­tion :

Use two for loops. Time Com­plex­ity O(N2).

Bet­ter Solu­tion: Using Hast­Set, Time Com­plex­ity O(N).

  • Take a vari­able say index = –1.
  • Ini­tial­ize a HashSet.
  • Nav­i­gate the array from right to left(backwards) tak­ing one ele­ment at a time
  • if Hash­Set doesnt con­tain ele­ment, add it
  • if Hash­Set con­tains then update the index with cur­rent index in navigation.
  • At the end index will be updated by the ele­ment which is repeated and has the low­est index.

Com­plete Code:


Out­put:

{1,2,5,7,5,3,10,2}
first repeated element by index is : 2

You may also like...

  • Bill

    Code is wrong
    a)left paren­the­sis miss­ing in System.out.println”{1,2,5,7,5,3,10,2}”);
    b) for loop needs to stop at i >=0 else it never enters as it is

    • tuto­ri­al­hori­zon

      Thanks bill. Cor­rected it.