LeetCode 49: Group Anagrams I'm exceeding the time limit for a 10,000 word test case provided on LeetCode:


  Given an array of strings, group anagrams together.
  
  For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
  Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

  
  Note: All inputs will be in lower-case.


Any suggestions on how I could speed this up a little bit?

public HashMap&lt;String, List&lt;Integer&gt;&gt; createMap(String[] strs)
{
  HashMap&lt;String, List&lt;Integer&gt;&gt; map = new HashMap&lt;String, List&lt;Integer&gt;&gt;();

    for(String s: strs)
    {
     char[] charArray = s.toCharArray();
     Arrays.sort(charArray);
     String sortedString = new String(charArray);

     if(map.containsKey(sortedString))
     {
        List&lt;Integer&gt; pos = map.get(sortedString);
        pos.add(Arrays.asList(strs).indexOf(s));
        map.put(sortedString, pos);
     }

    else
    {
        List&lt;Integer&gt; pos = new ArrayList&lt;Integer&gt;();
        pos.add(Arrays.asList(strs).indexOf(s));
        map.put(sortedString, pos);
    }
  }

  return map;
}

public List&lt;List&lt;String&gt;&gt; groupAnagrams(String[] strs) {

  HashMap hm = createMap(strs);

  List&lt;List&lt;String&gt;&gt; anagrams = new ArrayList&lt;List&lt;String&gt;&gt;();

  for(Object k: hm.keySet())
  {
    String key = k.toString();
    ArrayList pos = (ArrayList)hm.get(key);

    List&lt;String&gt; a = new ArrayList&lt;String&gt;();
    for(Object p : pos)
    {
      int idx = Integer.parseInt(p.toString());
      a.add(strs[idx]);
    }
    anagrams.add(a);
  }
  return anagrams;
}
Why so slow

It's important to consider the time complexity of all the operations in your program.

Take a closer looks at this part I extracted from your code:


for(String s: strs)
{
 // ...

    pos.add(Arrays.asList(strs).indexOf(s));



For each s, converting a String[] to a List&lt;String&gt;, in order to use the indexOf method to find the index of s? That doesn't sound so good. How about making that a counting loop?

for (int i = 0; i &lt; strs.length; i++) {
    // ...

    pos.add(i);


But why use indexes at all? Why not make this method return a Map&lt;String, List&lt;String&gt;&gt; instead?

for (String s : strs) {
    // ...

    pos.add(s);


If you do that, then the implementation of the other method becomes simply:

public List&lt;List&lt;String&gt;&gt; groupAnagrams(String[] strs) {
    return new ArrayList&lt;&gt;(createMap(strs).values());
}


Good practices

The code violates many good practices and common conventions:


Never use raw types, for example use HashMap&lt;String, List&lt;String&gt;&gt; instead of just HashMap without type parameters
Prefer to declare variables with interface types, for example Map&lt;String, List&lt;String&gt;&gt; instead of HashMap&lt;String, List&lt;String&gt;&gt;
Use the diamond operator &lt;&gt; when possible, for example new HashMap&lt;&gt; instead of new HashMap&lt;String, List&lt;String&gt;&gt;
Use consistent indentation, and please place braces they way I did in my examples above