0

I have this piece of code to find groups of anagrams as string arrays given an array of strings where n is the array length and m is the max string length.

func GroupAnagrams(strs []string) [][]string {
    res := [][]string{}

    m := map[[26]int][]string{}

    for _, s := range strs {

        a := [26]int{}
        for _, uc := range s {
            a[uc-'a']++
        }
        m[a] = append(m[a], s)
    }

    for _, v := range m {
        res = append(res, v)
    }

    return res
}

I think the big O for the first loop is O(mn). But the algorithm has to loop through the map to add up the results. So what is the big O for that?

Side question, anyone have a faster solution for this lol?

LeonAdvice
  • 73
  • 1
  • 7
  • 1
    You're correct about the first, *assuming* that `append` and map assignment / lookup are all O(1) or close enough to not worry about it. To think about the second: how many map entries can there be in `m`? If there are `n` strings and they're all the same length then there's just one `m` element (which has `n` items in it); if they are all different then there are `n` elements (each of which has 1 item in it); and for anything in between you get a mix of these. So we'll go through the loop itself at most n times. But what about `append` and map lookup? – torek May 01 '22 at 17:07
  • 1
    Well, `append` *could* be implemented badly, in which case it would be O(n*n) in the length of things appended. [But it's not, so it's O(n), with "amortized cost" O(1).](https://stackoverflow.com/q/22173998/1256452) And, map lookup/insert could be terrible, but it's not: it's generally O(1) as expected. We have to make some assumptions about the Go runtime here, but they're pretty safe. – torek May 01 '22 at 17:09

0 Answers0