Start learning free

LESSON 227 OF 414 · SORTING

Group Anagrams in Scala: O(n * log n * L * log L) with Sorting

Practice O(n * log 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:

For this lesson, your algorithm should run in O(n * log n * L * log L) time and use O(n * L) extra space, where n is the number of strings and L is the length of the longest string.
(There are faster solutions which we will discuss in future lessons)


STEP 1 OF 12
    Ctrl + Enter to check

    SCALA · SORTING

    Group Anagrams in Scala, explained

    Problem overview

    The method groupAnagrams receives an array of strings and returns them grouped so that each group holds strings made of exactly the same letters. The order of the groups, and of the strings inside a group, doesn't matter. The return type is List[List[String]].

    For ["eat", "tea", "tan", "ate", "nat", "bat"], the groups are eat, tea, ate, then tan, nat, then bat.

    Approach: sort the letters, sort the words

    Two strings are anagrams exactly when their letters, put in alphabetical order, give the same string. "eat", "tea" and "ate" all become "aet", while "tan" and "nat" become "ant". That sorted string is a key that is identical for every member of a group.

    Now sort the array of words by that key. Words with the same key end up next to each other, so each group is one block of neighbours. A single pass can then cut the sorted array into blocks: keep adding words to the current group, and when the next word has a different key (or there is no next word), the group is complete.

    With n words of length at most L, sorting one word's letters costs O(L log L). Sorting the array makes O(n log n) comparisons, and each comparison computes two keys, so the cost is O(n log n * L log L), the bound in the statement. Space is O(n * L) for the sorted copy and the groups. Later lessons replace this with a hash map.

    Step by step

    1. Assume a helper sorted(s) that returns the letters of s in alphabetical order. It is written at the end.
    2. Sort the words by key. strings.sortBy(s => sorted(s)) returns a new array in which anagrams are adjacent. The original array is unchanged.
    3. Prepare the output. result is a val holding a ListBuffer of finished groups. A buffer can grow by appending, which a List can't do cheaply.
    4. Prepare the current group. currentGroup is a var holding a ListBuffer, because the variable will be pointed at a fresh buffer after every group.
    5. Loop over the positions of the sorted array with strs.indices.
    6. Add the word to the current group. In sorted order it always belongs to the group being built.
    7. Detect the end of a group. The group ends when i is the last index, or when the key of strs(i) differs from the key of strs(i + 1). The last-index test comes first: || doesn't evaluate its right side when the left side is true, so strs(i + 1) is never read past the end.
    8. Close the group. Append currentGroup.toList to result, then start a new empty buffer.
    9. Return result.toList.
    10. Write the helper. Copy the characters with s.toCharArray, because a string is immutable and can't be sorted in place. Sort the copy with java.util.Arrays.sort, then build a string from it with new String(temp).

    The solution in Scala

    class Solution {
    def sorted(s: String): String = {
        val temp = s.toCharArray
        java.util.Arrays.sort(temp)
        new String(temp)
    }

    def groupAnagrams(strings: Array[String]): List[List[String]] = {
        val strs = strings.sortBy(s => sorted(s))
        val result = scala.collection.mutable.ListBuffer.empty[List[String]]
        var currentGroup = scala.collection.mutable.ListBuffer.empty[String]
        for (i <- strs.indices) {
            currentGroup += strs(i)
            if (i == strs.length - 1 || sorted(strs(i)) != sorted(strs(i + 1))) {
                result += currentGroup.toList
                currentGroup = scala.collection.mutable.ListBuffer.empty[String]
            }
        }
        result.toList
    }
}

    The Scala details worth knowing:

    • Scala uses Java's library. toCharArray and java.util.Arrays.sort come straight from Java, and new String(temp) calls Java's String constructor. Scala can call any Java class without a wrapper.
    • The helper's name. The method is called sorted, like the collection method. Inside the class, sorted(s) with a string argument refers to this helper, while strings.sortBy(...) is unrelated to it.
    • sortBy returns a new array. The result is a sorted copy, and it is stable: words with equal keys keep their input order. In the example, the group comes out as eat, tea, ate, the input order.
    • == and != compare string contents. There is no need for equals.
    • strs.indices is the range 0 until strs.length.
    • toList makes an immutable copy. The group is copied into a List before the buffer is replaced, which matches the return type and means later changes to a buffer can't alter a finished group.
    • Last expression. new String(temp) and result.toList are the values of their methods; no return is written.

    Complexity

    Let n be the number of strings and L the length of the longest one.

    Time: O(n * log n * L * log L). The sort does O(n log n) comparisons, and each recomputes two keys at O(L log L). The grouping pass computes two keys per index, which is O(n * L log L) and is already covered by the first term.

    Space: O(n * L). The sorted array of references, the lists of strings and the temporary key arrays each stay within that bound.

    Edge cases and common mistakes

    • Empty array. The loop doesn't run and the result is an empty list.
    • Empty strings. [""] gives one group that holds the empty string. All empty strings share the key "".
    • Single words. A word with no anagram forms a group of one, like bat.
    • Repeated words. Two equal strings are anagrams of each other and share a group.
    • Case. "Eat" and "tea" have different keys, because uppercase letters sort before lowercase ones. The comparison is exact.
    • Reading past the end. Testing sorted(strs(i)) != sorted(strs(i + 1)) before i == strs.length - 1 throws an ArrayIndexOutOfBoundsException on the last word.
    • Reusing one buffer. Skipping the line that creates a new currentGroup would keep adding later groups to the first one.
    • Sorting the words themselves. The output must contain the original words. The sorted letters are only the key.

    Testing

    • ["eat", "tea", "tan", "ate", "nat", "bat"] gives [[bat], [eat, tea, ate], [tan, nat]].
    • [] gives [].
    • [""] gives one group containing the empty string.
    • ["a"] gives [[a]].
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free