LESSON 204 OF 348 · SORTING

Group Anagrams in Kotlin: 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.
(There are faster solutions which we will discuss in future lessons)

STEP 1 OF 12

Guided

Ctrl + Enter to check

Group Anagrams in Kotlin, explained

Problem overview

Given an Array<String> named strings, groupAnagrams returns a List<List<String>> in which words made of the same letters are grouped together. Two words are anagrams when one is a rearrangement of the other, using every letter exactly once. The groups and the words inside them may come back in any order.

For ["eat", "tea", "tan", "ate", "nat", "bat"] there are three groups: eat, tea, ate, then tan, nat, and then bat alone.

Approach

Comparing every pair of words to see if they are anagrams is slow and awkward. A better idea is to give each word a key that is the same for all its anagrams: the word's letters in alphabetical order. eat, tea and ate all become aet, while tan and nat become ant. Two words are anagrams exactly when their keys match.

The lesson then sorts the whole array by this key. All words with the same key end up next to each other, so each group is a block of neighbours. One pass over the sorted words can cut the blocks apart: a group ends when the next word's key is different, or when the words run out.

Sorting n words costs O(n log n) comparisons. Each comparison here builds two keys, and sorting the letters of a word of length L costs O(L log L). That gives O(n log n * L log L) time, the bound the lesson states, with O(n * L) space for the sorted copy and the groups. Faster solutions that count letters or use a map come in later lessons.

Step by step

Start with the key helper, as the lesson does: assume a function sorted(s) exists and write it at the end.

Sort the words by key. val strs = strings.sortedWith(compareBy { sorted(it) }). compareBy builds a comparator from a lambda that picks the sort key, and it is the single lambda parameter, the word. sortedWith returns a new List, so strings is left unchanged.
Create result as an empty ArrayList<List<String>> that will collect finished groups.
Create currentGroup as a var holding an empty ArrayList<String>. It must be a var because it gets replaced after each group.
Loop over strs.indices with an index i, so each word can be compared with the next one.
Add strs[i] to currentGroup. In sorted order, the current word always belongs to the group being built.
Detect the end of a group. The test is i == strs.size - 1 || sorted(strs[i]) != sorted(strs[i + 1]). Either this is the last word, or the next word has a different key. The last-index check comes first because || skips its right side when the left side is true, so strs[i + 1] is never read past the end.
Store the group and start a new one. Add currentGroup to result, then assign a fresh ArrayList(). Calling clear() instead would also empty the group already stored, because both names refer to the same list object.
Return result.
Write the helper sorted(s) inside the class. Turn the string into characters with s.toCharArray(), since strings are immutable and can't be sorted in place. Sort that array with sort(), and build the key with String(temp).

The solution in Kotlin

class Solution {
    fun sorted(s: String): String {
        val temp = s.toCharArray()
        temp.sort()
        return String(temp)
    }

    fun groupAnagrams(strings: Array<String>): List<List<String>> {
        val strs = strings.sortedWith(compareBy { sorted(it) })
        val result = ArrayList<List<String>>()
        var currentGroup = ArrayList<String>()
        for (i in strs.indices) {
            currentGroup.add(strs[i])
            if (i == strs.size - 1 || sorted(strs[i]) != sorted(strs[i + 1])) {
                result.add(currentGroup)
                currentGroup = ArrayList()
            }
        }
        return result
    }
}

Kotlin details worth knowing:

On strings, == and != compare contents, so sorted(a) != sorted(b) is the right way to compare keys.
The method named sorted in the class is a different function from the standard library's sorted(), which is called on a collection. Inside compareBy, sorted(it) with an argument resolves to the class's own method.
String(temp) builds a string from a CharArray. Printing the array itself would show a reference-style text instead of the letters.
sortedWith is stable: words with the same key keep their input order. For the example it gives the groups in key order, bat, then eat, tea, ate, then tan, nat.
The type of ArrayList() on the line currentGroup = ArrayList() is inferred from the declaration of currentGroup. An ArrayList<String> can be added to result because it is a List<String>.

Complexity

Time: O(n log n * L log L), as explained above. The final pass makes O(n) more key computations, which doesn't change the bound.
Space: O(n * L) for the sorted copy of the words and the result lists, plus O(L) for each temporary key.

Edge cases and common mistakes

Empty array. The loop doesn't run and the result is an empty list.
Empty string. Its key is the empty string, and all empty strings group together.
Single word. It is the last index, so it forms its own group.
Forgetting the final group. A check that only looks at the next word would never close the last group. The i == strs.size - 1 case handles that.
Reusing one list. Calling currentGroup.clear() after adding it to result empties the stored group too.
Different case. "Eat" and "tea" have different keys, because uppercase letters sort before lowercase ones. The lesson's words are lowercase.

Testing

["eat", "tea", "tan", "ate", "nat", "bat"] returns [[bat], [eat, tea, ate], [tan, nat]].
["abc"] returns [[abc]].
["ab", "ba", "ab"] returns one group holding all three words.

Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free