0
$\begingroup$

My question comes from solving this LeetCode question, in which we are given a string of characters with size N, and one of the solutions is to use a hashmap (dictionary in Python) to count the characters, with the character being the key, and the count being the value.

For instance, "abbcddd" results in a hashmap {'a':1, 'b':2, "c":1, "d":3}. This is the second solution given by LeetCode.

I thought the space complexity of this solution is O(N), because if the string has all unique characters, we will need the hashmap to have N keys. However, the solution says the space complexity is O(1), because

Space complexity : O(1). The map can grow up to a maximum number of all distinct elements. However, the number of distinct characters are bounded, so as the space complexity.

Then I have this follow up question - if a problem requires me to create a deep copy of a string (or an array) of size N, does it take space O(N) or O(1)? Is it O(1) because the maximum length of the copied string/array is bounded by the original string/array?

Thanks.

$\endgroup$
9
  • 1
    $\begingroup$ LeetCode is not a reliable source. $\endgroup$ Feb 27, 2022 at 16:10
  • $\begingroup$ Thank you for your insights! May I proceed to ask, based on your understanding, should the leetcode problem and my question both take space complexity O(N)? Thanks a lot! $\endgroup$
    – Hang Chen
    Feb 27, 2022 at 17:49
  • $\begingroup$ Since there are only $O(1)$ possible letters, the hash table should take up $O(1)$ space. $\endgroup$ Feb 27, 2022 at 17:58
  • $\begingroup$ May I ask why should we regard it as O(1) possible letters? The worst case is that all letters are unique. Isn't that O(N)? Just because we know the maximum number of letters (upper bound), we treat it as O(1)? $\endgroup$
    – Hang Chen
    Feb 27, 2022 at 18:21
  • $\begingroup$ Assuming that each letter is one byte, there are only 256 possible letters. $\endgroup$ Feb 27, 2022 at 18:22

2 Answers 2

2
$\begingroup$

If the output of the algorithm is the deep-copied string, the complexity is O(1), because you don't count the input nor output space.

If the copy is used for internal purposes, then the complexity is at least O(N).

But this is unrelated to the LeetCode question, which does not require a deep copy. (The required space is bounded by the alphabet size.)

$\endgroup$
1
  • $\begingroup$ Awesome! Thanks for your insight! This is now very much clear! $\endgroup$
    – Hang Chen
    Feb 28, 2022 at 16:02
1
$\begingroup$

I thought the space complexity of this solution is O(N), because if the string has all unique characters, we will need the hashmap to have N keys

Remember, big-O tells you the tendency as N goes to infinity. If a string has more than around 2^21 characters (assuming valid Unicode) they can't all be unique, by the pigeonhole principle, so as N increases beyond this point, the number of elements in the map stops growing — the definition of O(1).

$\endgroup$
1
  • $\begingroup$ Oh! Cool, this definitely convinced me more!! $\endgroup$
    – Hang Chen
    Feb 28, 2022 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.