Why does this Python O(n) solution execute so much slower than the others?


  • 0
    F

    I don't want to use built-in sort() or most_common() because I consider that cheating. My solution is O(n) as far as I can tell, and so are the others, but mine executes way way slower than the rest (it beats like 0.8%).

    Is built-in sort() and most_common() really the only explanation, or am I missing something here?

    class Solution(object):
        def frequencySort(self, s):
            """
            :type s: str
            :rtype: str
            """
            frequencies = [[] for _ in range(len(s))]
            counts = {}
            for c in s:
                if c not in counts:
                    counts[c] = 0
                counts[c] += 1
            for c in counts:
                frequencies[counts[c]-1].append(c)
            result = []
            for i in range(len(frequencies) - 1, -1, -1):
                for c in frequencies[i]:
                    result += [c] * (i + 1)
            return result

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.