Given an array of integers, find minimum index of a repeating element in linear time and doing just one traversal of the array.
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.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <iostream> #include <unordered_set> using namespace std; // Function to find minimum index of repeating element int findMinIndex(int arr[], int n) { int minIndex = n; // create an empty set to store array elements unordered_set<int> set; // traverse array from right to left for (int i = n - 1; i >= 0; i--) { // if the element is seen before, update minimum index if (set.find(arr[i]) != set.end()) minIndex = i; // if the element is seen for the first time, insert it into set else set.insert(arr[i]); } // return minimum index return minIndex; } // main function int main() { int arr[] = { 5, 6, 3, 4, 3, 6, 4 }; // int arr[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]); int minIndex = findMinIndex(arr, n); if (minIndex != n) cout << "Minimum index of repeating element is " << minIndex; else cout << "Invalid Input"; return 0; } |
Output:
Minimum index of repeating element is 1
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
import java.util.HashSet; import java.util.Set; class Util { // Function to find minimum index of repeating element public static int findMinIndex(int[] A) { int minIndex = A.length; // create an empty set to store array elements Set<Integer> set = new HashSet<>(); // traverse array from right to left for (int i = A.length - 1; i >= 0; i--) { // if the element is seen before, update minimum index if (set.contains(A[i])) { minIndex = i; } // if the element is seen for the first time, insert it into set else { set.add(A[i]); } } // return minimum index return minIndex; } // main function public static void main(String[] args) { int[] A = { 5, 6, 3, 4, 3, 6, 4 }; // int[] A = { 1, 2, 3, 4, 5, 6 }; int minIndex = findMinIndex(A); if (minIndex != A.length) { System.out.print("Minimum index of repeating element is " + minIndex); } else { System.out.print("Invalid Input"); } } } |
Output:
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).
Thanks for reading.
Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
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.
https://ideone.com/g8tl7H
https://ideone.com/cD22NX