Start learning free

LESSON 243 OF 338 · HASH TABLE

Group Anagrams in Go: O(n * L * log L) by Sorting Each Word

Practice O(n * L * log L) Read the full explanation

Given an array of strings, group the anagrams together. You can return the answer in any order.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

Example:

Input:   strings = ["eat","tea","tan","ate","nat","bat"]

Output:  [["bat"],["nat","tan"],["ate","eat","tea"]]

Note:

Your algorithm should run in O(n * L * log L) time and use O(n * L) extra space.


STEP 1 OF 9
    Ctrl + Enter to check

    GO · HASH TABLE

    Group Anagrams in Go, explained

    Problem overview

    The method groupAnagrams receives a slice of strings, strs, and returns a slice of groups, where every group holds the words that are anagrams of each other: the same letters, rearranged. The groups may come back in any order.

    For ["eat", "tea", "tan", "ate", "nat", "bat"] the groups are eat, tea, ate, then tan, nat, then bat. The example in the statement lists them in a different order, which is fine.

    The budget is O(n * L * log L) time and O(n * L) extra space, where n is the number of words and L is the length of the longest word.

    Approach: use the sorted word as a key

    Comparing every pair of words to see whether they are anagrams would take about n² comparisons. The faster idea is to give every word a label that is the same for all its anagrams and different for everything else. Sorting the letters does exactly that: eat, tea and ate all become aet, while tan and nat become ant.

    A map from that label to the list of words that produced it does the grouping. Each word is sorted once, which costs O(L log L), and inserted in the map in about O(L) for hashing the key. After one pass over all words, each map value is a finished group.

    Step by step

    1. Declare the map. groupBySorted maps a sorted string to a slice of the original words. An empty map literal is ready to use.
    2. Loop over the words. The index is not needed, so it is discarded with _.
    3. Copy the word into a byte slice. A Go string can't be modified in place, so the letters are copied into chars to be sorted.
    4. Sort the bytes and turn them back into a string. sort.Slice takes the slice and a function that says whether the element at index i goes before the one at j. Converting chars to a string makes the key, since slices can't be map keys but strings can.
    5. Add the original word to its group. Append s (not the sorted text) under the key and store the result back in the map.
    6. Collect the groups. Make an empty [][]string called result and loop over the map's values, appending each group.
    7. Return result.

    The solution in Go

    func (sol Solution) groupAnagrams(strs []string) [][]string {
    groupBySorted := map[string][]string{}
    for _, s := range strs {
        chars := []byte(s)
        sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })
        sortedString := string(chars)
        groupBySorted[sortedString] = append(groupBySorted[sortedString], s)
    }
    result := [][]string{}
    for _, words := range groupBySorted {
        result = append(result, words)
    }
    return result
}

    Go details in this code

    • The method on Solution. (sol Solution) is the receiver: groupAnagrams is attached to the Solution type, and the receiver isn't used in the body. The code also needs the sort package imported.
    • Strings are immutable. []byte(s) makes a copy, so sorting chars never changes s, which is why the original word can still be appended later.
    • Bytes, not letters. A string indexes as bytes, so this sorts bytes. That is exactly right for ASCII words such as the lowercase English ones in this problem, where one letter is one byte.
    • sort.Slice needs a less function, and it sorts in place. It returns nothing, so there is no result to assign.
    • Appending to a missing key works. Reading a missing key from a map gives the zero value, and for a slice that is nil. append(nil, s) creates a new slice with one element. The result of append must be stored back, because the slice may have been reallocated.
    • Map iteration order is random. The groups come out in a different order from run to run, and so does the order of the groups in the result. That is allowed here, since the problem accepts any order. The words inside a group keep the order of the input.

    Complexity

    Time: O(n * L * log L). Each of the n words is copied in O(L), sorted in O(L log L), converted to a string in O(L), and hashed in O(L). Sorting dominates. Collecting the groups takes O(n).

    Space: O(n * L). The map stores a key of length up to L per distinct group and keeps every original word in some group.

    Edge cases and common mistakes

    • Empty input. A nil or empty strs gives an empty result. Because result is created as [][]string{}, it is an empty slice rather than nil.
    • The empty string. Its sorted form is also the empty string, so [""] gives one group containing the empty word.
    • Words that are the same. Duplicates such as "abc" twice land in the same group, once each.
    • Same letters, different counts. "aab" and "ab" sort to aab and ab, which differ, so they are correctly kept apart.
    • Appending the sorted text. The groups must contain the original words, not their keys.
    • Expecting a fixed order. Comparing the result to a hard-coded order of groups fails at random because of map iteration. Compare groups regardless of their order.
    • Forgetting to assign append. Calling append without storing its result discards the new element.

    Testing

    • ["eat", "tea", "tan", "ate", "nat", "bat"] gives three groups: eat, tea, ate; tan, nat; bat.
    • [""] gives one group with one empty string.
    • [] gives no groups.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free