This post is completed by 1 user

  • 0
 Add to List
Medium

50. Find the first repeated element in an array by its index

Objective: Given an array of integers, find out the first repeated element. The first repeated element means the element occurs at least twice and has the 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

Approach:

Naive Solution :

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

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

  1. Take a variable say index = -1.
  2. Initialize a HashSet.
  3. Navigate the array from right to left(backward) taking one element at a time
  4. if HashSet doesn't contain the element, add it
  5. if HashSet contains then update the index with the current index in navigation.
  6. At the end, the the index will be updated by the repeated element with the lowest index.

Output:

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

Related Problems: