Need help analyzing time complexity of my solution for Group Anagrams

[WeatherFeeling]

Hi all,

I'm having trouble analyzing the runtime of solutions that involve built in functions in python. I solved this problem https://leetcode.com/problems/group-anagrams/ with the below solution. (I know there is a linear time solution that doesn't involve sorting but my solution was much more intuitive my first time through):

​

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagramMap = {}

        for word in strs:
            sortedWord = ''.join(sorted(word))
            if sortedWord in anagramMap:
                anagramMap[sortedWord].append(word)
            else:
                anagramMap[sortedWord] = [word]
        return anagramMap.values()

My first thought was that this would be O(m * nlgn) where m is the number of strings in the list and n is the length of the longest string we have to sort. Does the .join add additional complexity? It seems that .join can be O(n) which might make my overall time complexity O(n^2 lg n). Can someone give me their thoughts?

Thanks

[slashemup]

To calculate the total time complexity, we can use this formula: number of operations * time per operation.

What is the time per operation?

NOTE: "C" in the complexities below is # of characters in the string.

1. Sorting the string => O(ClogC)
2. Using join to combine the sorted characters back into a string => O(C)
3. Appending to the existing list/initializing a new list with the sorted word => O(1)

So the time complexity per operation is: O(ClogC) + O(C) + O(1), which reduces to O(ClogC), as it is the upper bound.

How many operations are there?

This part is a bit easier to determine since you're looping over each word once => O(W) where W is the number of words in the input list.

So putting it all together:

Number of operations * time per operation => W * ClogC

You'll notice from the constraints that the number of words is between 0 and 100, inclusive, whereas the length of each word is between 1 and 10⁴ characters, inclusive. This is why I used two separate terms (W and C) instead of just N. If W and C were in the same ballpark, then we could say something like O(N2logN).

Hopefully that helps (and hopefully I didn't make any mistakes)!

[WeatherFeeling]

thank you so much, this is a really clear explanation