Grouping anagrams together from a string array

Question

I wrote this code in c#. It is a question from LeetCode, number 49. Given an array of strings, group the anagrams.

The examples it gives are:

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

then return:

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

I am wondering what exactly my time complexity is? I believe it is O(2n) which becomes O(n) after dropping the constant. But I am also thinking it might actually be O(2n^2) or O(n^2) because in my first for loop I have Array.Sort(new string(temp)) which may increase the time complexity. Please let me know.

Overall, how can I improve and speed up my code? Maybe I could get rid of the dictionary? Get rid of Array.Sort(new string(temp))? Create one instance of new string(temp) and use the variable instead? I am also thinking I should move everything into one for loop. How could this best be accomplished?

public IList<IList<string>> GroupAnagrams(string[] strs)
{
 IList<IList<string>> ans = new List<IList<string>>();
 Dictionary<string, List<string>> values = new Dictionary<string, List<string>>();
 for (int i = 0; i < strs.Length; i++){
 char[] temp = strs[i].ToCharArray();
 Array.Sort(new string(temp));
 if (!values.ContainsKey(new string(temp)))
 values.Add(new string(temp), new List<string> { strs[i] });
 else
 values[new string(temp)].Add(strs[i]);
 }
 for (int i = 0; i < values.Count; i++){
 ans.Add(values.ElementAt(i).Value);
 return ans;
 }

• Martin Verjans: Array.Sort(new string(temp)); -> Impossible to convert from "string" to "System.Array".
• lukstru: generally, (standard) sorting algorithms have n*log n complexity. So it would be n * (n * log n) + n, which is O(n^2 * log n)
• lukstru: also it looks like you don't really need temp as a char array, so you could wrap the new string() around strs[i].ToCharArray(). EDIT: why even use .ToCharArray()?

Answer 1

Here is my 4 lines long alternative:

var anagrams = from word in words
 let pair = new { Original = word, AlphabeticallyOrdered = string.Concat(word.OrderBy(@char => @char)) }
 group pair by pair.AlphabeticallyOrdered into anagram
 select anagram.Select(@group => @group.Original);

Here are my line by line explanations:

1. Iterate through the received words
2. Create a new string pair where we store the original word and the alphabetically ordered version
3. Group them based on the alphabetically ordered version
4. Retrieve them based on the original version

---

If I iterate the result like this:

foreach(var anagram in anagrams)
{
 Console.WriteLine(string.Join(",", anagram));
}

the output will look like that:

eat,tea,ate
tan,nat
bat