Find Minimum Index of Repeating Element in an Array

Given an array of integers, find minimum index of a repeating element in linear time and doing just one traversal of the array.


For example,

Input:  { 5, 6, 3, 4, 3, 6, 4 }
Output: Minimum index of repeating element is 1

Input:  { 1, 2, 3, 4, 5, 6 }
Output: Invalid Input

Naive solution would be to consider each element arr[i] present in the array and search it in the sub-array arr[i+1..n-1]. We return its index as soon as duplicate is found. The implementation can be seen here, and takes O(n2) time.

We can use hashing to solve this problem in linear time. The idea is to traverse array from right to left. If the element is seen for the first time, we insert it into set else we update minimum index to element’s index. Finally, we return the minimum index after all elements are processed.


Download   Run Code


Minimum index of repeating element is 1


Download   Run Code


Minimum index of repeating element is 1

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

Or you can just do hashing from the start, key would be an element and value would be index. If element exist in map -> you return saved index.