First repeating element in O(n)

First repeating element in O(n)

  June 08, 2017    

---

Problem : Find First repeating element 

Although this problem can be easily solved with O(n^2) time and here i used map to solve in O(n).


import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
public static void main (String[] args)
{
   
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   boolean flag=false;
   int count=0;
   int n=ab.nextInt();
   int i=0;
   Map<Integer,Integer> map=new LinkedHashMap<Integer,Integer>();
   while(i++<n)
   {
       int temp=ab.nextInt();
       if(map.containsKey(temp))
       {
           map.put(temp,map.get(temp)+1);
       }
       else
       map.put(temp,0);
   }
   Set set = map.entrySet();
     
      // Get an iterator
      Iterator o = set.iterator();
     
      // Display elements
      while(o.hasNext()) {
          count++;
         Map.Entry me = (Map.Entry)o.next();
         int val=(int)me.getValue();
         if(val>0)
         {
             System.out.println(count);
             flag=true;
             break;
         }
      }
      while(!flag)
      System.out.println("-1");
}
}
}