CODEWITHSUNDEEP
pythonspace-complexity
chilliefiber
chilliefiber

Reputation: 651

Space complexity of grouping anagrams with hashmap

I'm solving a leetcode question.

Q: Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.

Note: strs[i] is made up of lowercase English letters

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # O(m*n) time complexity
        # O(m*n) space complexity
        d = {} # O(m) entries each with O(n) size
        for s in strs: # O(m)
            s_l = [0] * 26
            for c in s: # O(n)
                s_l[ord(c) - ord("a")] += 1
            t_l = tuple(s_l) # this is O(1) entry size with O(m) tuples
            if t_l in d:
                d[t_l].append(s)
            else:
                d[t_l] = [s]
        return d.values()

So, I thought the space complexity is O(m*n). There are O(m) entries in the dictionary, and each entry will have O(n) space, where m is the number of strings, and n is the length of the largest string (worst case is all the strings are the same length).

However, the solution I found in https://neetcode.io/problems/anagram-groups says the space complexity is O(m). Why?

Note that I have found many questions with this exact same problem, like [0] through [9] but none pertains to the space complexity.

  1. Grouping anagrams
  2. get list of anagrams from a dictionary
  3. Group Anagrams - LeetCode
  4. LeetCode 49 Group Anagrams
  5. Group anagrams in leetcode without sorting
  6. How to group anagrams in a string into an array
  7. Group together all the anagrams
  8. Group anagrams Leetcode question (python) this one also uses the solution for neetcode. No mention of space complexity unfortunately
  9. big O of group anagram algorithm
  10. How do I group different anagrams together from a given string array?

This question: String anagrams grouping | Improvements and Analyzing time complexity also agrees with my space complexity, but sadly there are no answers so I don't know who is right, if me and the questioner or neetcode.

Upvotes: 1

Views: 85

Answers (1)

Barmar
Barmar

Reputation: 782158

The space used by the string contents comes from the input. You're not making copies of the strings in the d dictionary, just references to the input strings. So this is not considered part of the space complexity of the algorithm.

Upvotes: -1

Related Questions