educative.io

Educative

Space complexity for representing char counts

This problem and many others involve building a hash map of (alphabetical) character frequencies. What’s the space complexity of the map?

At first glance it’s constant because there are at most 26 keys, and therefore 26 items, and a constant number of items consumes constant space.

At second glance, if our counts get large, then the space to store those counts will expand, theoretically to log(count) bits. Would the total space complexity would be logn?


Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Solution: Reorganize String

1 Like

Hello @Isaac_Haseley,

The space complexity of a hash map storing the frequencies of alphabetical characters is considered O(1), or constant. This is because there are at most 26 alphabetical characters, so the number of keys in the hash map is fixed and independent of the input size.

Although the space needed to store each count could theoretically grow (log(count) bits for large counts), in practical scenarios with fixed-size integers (like 32-bit or 64-bit), this space is constant. And even if you consider dynamically growing integers for extremely large counts (theoretically), since the number of keys is fixed (26 for the alphabet), the total space complexity of the hash map does not exceed O(1).

I hope this explanation helps in understanding the space complexity of building a hash map. If you have any other queries feel free to ask. We’d be happy to help. Thanks!

Happy learning!

Thanks @Dian_Us_Suqlain! I ask because 1) I’ve had some more theoretically-oriented interviewers (e.g. Google) ask that I assume infinite size of inputs along every dimension, and 2) This course is in Python, where ints dynamically grow in space with their counts.

And even if you consider dynamically growing integers for extremely large counts (theoretically), since the number of keys is fixed (26 for the alphabet), the total space complexity of the hash map does not exceed O(1).

Could a single key-value pair reach O(log(n)) size if its count is large?