title: Java problem time limit exceeded issue
body: <p>Im coding a problem(reference --http://www.codechef.com/FEB11/problems/THREECLR/)</p>
  
  <p>The below is my code</p>
  
  <pre><code>import java.io.*;
  import java.util.*;
  
  
  public class Main {
  
   static String ReadLn (int maxLg)  // utility function to read from stdin
      {
          byte lin[] = new byte [maxLg];
          int lg = 0, car = -1;
          String line = "";
  
          try
          {
              while (lg &lt; maxLg)
              {
                  car = System.in.read();
                  if ((car &lt; 0) || (car == '\n')) break;
                  lin [lg++] += car;
              }
          }
          catch (IOException e)
          {
              return (null);
          }
  
          if ((car &lt; 0) &amp;&amp; (lg == 0)) return (null);  // eof
          return (new String (lin, 0, lg));
      }
  
   public static boolean iscontains(HashMap&lt;Integer,HashSet&lt;Integer&gt;&gt; resultmap,HashSet&lt;Integer&gt; b, int index)
   {
       boolean result=false;
       for(Iterator&lt;Integer&gt; iter = b.iterator();iter.hasNext();)
          {  int tmp=Integer.valueOf(iter.next().toString());
              if(resultmap.get(index).contains(tmp))
                      result=true;                
          }
  
       return result;
   }
  
  
  public static void main(String[] args) throws InterruptedException, FileNotFoundException {
      try {
  
      HashMap&lt;Integer,HashSet&lt;Integer&gt;&gt; pairlist = new HashMap&lt;Integer,HashSet&lt;Integer&gt;&gt;();
       String input=null;
       StringTokenizer idata;
       int tc=0;
      input=Main.ReadLn(255);
      tc=Integer.parseInt(input);
      while(--tc&gt;=0)
      {
          input=Main.ReadLn(255);
          idata = new StringTokenizer (input);idata = new StringTokenizer (input);
          int dishnum= Integer.parseInt(idata.nextToken());
          int pairnum= Integer.parseInt(idata.nextToken());
          while (--pairnum&gt;=0)
          {
              input=Main.ReadLn(255);
              idata = new StringTokenizer (input);idata = new StringTokenizer (input);
              int dish1=Integer.parseInt(idata.nextToken());
              int dish2=Integer.parseInt(idata.nextToken());
              if(pairlist.containsKey((Integer)dish1))
              {
                  HashSet&lt;Integer&gt; dishes=new HashSet&lt;Integer&gt;();
                  dishes=pairlist.get(dish1);
                  dishes.add(dish2);
                  pairlist.put(dish1, dishes);
              }
              else
              {
                  HashSet&lt;Integer&gt; dishes=new HashSet&lt;Integer&gt;();
                  dishes.add(dish2);
                  pairlist.put(dish1, dishes);
              }
          }
          int maxrounds=1;
          HashMap&lt;Integer,HashSet&lt;Integer&gt;&gt; resultlist = new HashMap&lt;Integer,HashSet&lt;Integer&gt;&gt;();
          HashSet&lt;Integer&gt; addresult=new HashSet&lt;Integer&gt;();
          addresult.add(1);
          resultlist.put(1,addresult);
          System.out.print("1");
          for(int i=2;i&lt;=dishnum;i++)
          {
              boolean found_one=false;
              boolean second_check=false;
              int minroundnum=maxrounds;
              boolean pairlistcontains=false;
              pairlistcontains=pairlist.containsKey(i);
              for(int j=maxrounds;j&gt;=1;j--)
              {
                  if(!found_one){
                  if(pairlistcontains)
                  {
                      if(!iscontains(resultlist,pairlist.get((Integer) i),j))
                      {
                           for(Iterator&lt;Integer&gt; resultiter = resultlist.get(j).iterator();resultiter.hasNext();)
                           {
                               if(pairlist.get(resultiter.next()).contains(i))
                                   second_check=true;  
                           }
                           if(second_check==false)
                           {
                               found_one=true;
                               minroundnum=j;
                               j=0;
                               //second_check=false;
                           }
                      }
  
                  }
                  else
                  {
                       for(Iterator&lt;Integer&gt; resultiter = resultlist.get(j).iterator();resultiter.hasNext();)
                       {
                           if(pairlist.get(resultiter.next()).contains(i))
                               second_check=true;  
                       }
                       if(second_check==false)
                       {
                           found_one=true;
                           minroundnum=j;
                           j=0;
                           //second_check=false;
                       }
  
                  }
                  second_check=false;
  
  
              }
          }
              if((minroundnum==maxrounds)&amp;&amp;(found_one==false))
                  {
                  ++minroundnum;
                  ++maxrounds;
                  }
              else
              {
                  found_one=false;
              }
              HashSet&lt;Integer&gt; add2list=new HashSet&lt;Integer&gt; ();
              if(resultlist.containsKey(minroundnum))
              {
                  add2list=resultlist.get(minroundnum);
                  add2list.add(i);
              }
              else
              {
                  add2list.add(i);
              }
              resultlist.put(minroundnum,add2list);
              System.out.print(" ");
              System.out.print(minroundnum);
  
  
          }
          if((tc !=-1))
              System.out.println();
  
      }
  
  
      }
      catch(Exception e){System.out.println(e.toString());}
  }}
  </code></pre>
  
  <p>I have checked this code on online judges like Ideone and have been getting the desired results. But when i submit this code, I get a Time Limit exceeded error. I have tested this code on Ideone with a sufficiently large set of input and the time taken to execute was lesser than 1 second. It seems to have a bug or a memory leak that seems to have drained all the happiness from my life.
  Any pointers/tips would be greatly appreciated.</p>
  
  <p>Thanks </p>
  
  <p>EDIT1 --</p>
  
  <p>Thanks for the replies guys, I ran the code with the input generated by the following python script --</p>
  
  <pre><code>import random
  filename="input.txt"
  file=open(filename,'w')
  file.write("50")
  file.write("\n")
  for i in range(0,50):
          file.write("500 10000")
          file.write("\n")
          for j in range(0,10000):
                  file.write(str(random.randrange(1,501))+" "+str(random.randrange(1,501)))
                  file.write("\n")
  file.close()
  </code></pre>
  
  <p>And my code took a whopping 71052 milliseconds to execute on the input provided by the above script. I have to now get down the execution time to 8000 milliseconds to the very least.
  Im working on trying out replacing the HashMaps and the HashSets as suggested by rfeak and am also wondering if memoization would help in this scenario. Please advise.</p>
  
  <p>EDIT2 --
  Recoding my algo using arrays seems to have worked. Only just though, resubmitting the same code at different times gives me Accepted Solution and Time limit exceeded :D I have though of another way to use hashmaps to optimize a little further.
  Thanks a load for the help guys !</p>