Kotlin maps: counting and indexing

Count words with groupingBy and build a lookup map with getOrPut.

fun main() {
    val text = "the cat and the hat and the bat"
    val freq = text.split(" ").groupingBy { it }.eachCount()
    println(freq.entries.sortedWith(compareBy({ -it.value }, { it.key })).joinToString(" ") { "${it.key}=${it.value}" })

    val index = mutableMapOf<Char, MutableList<String>>()
    for (word in listOf("apple", "avocado", "banana", "blueberry", "cherry")) {
        index.getOrPut(word[0]) { mutableListOf() }.add(word)
    }
    println(index)
    println(index['b']?.size ?: 0)
    println(index['z']?.size ?: 0)
}

the=3 and=2 bat=1 cat=1 hat=1
{a=[apple, avocado], b=[banana, blueberry], c=[cherry]}
2
0

Explanation

Kotlin has read-only Map and MutableMap types. mapOf and mutableMapOf keep the order of insertion when printed. groupingBy { key }.eachCount() counts how many elements share each key in one pass. getOrPut(key) { default } returns the existing value or creates and stores a new one, which is the clean way to build a map of lists.

The word-frequency map is sorted by count, highest first, with ties broken by the word, using compareBy with negative counts. The index map groups words by their first letter. Both run in O(n) apart from the sorting, because map lookups take O(1) on average.

—

the=3 and=2 bat=1 cat=1 hat=1

the=3 and=2 bat=1 cat=1 hat=1

the=3 and=2 bat=1 cat=1 hat=1
{a=[apple, avocado], b=[banana, blueberry], c=[cherry]}

the=3 and=2 bat=1 cat=1 hat=1
{a=[apple, avocado], b=[banana, blueberry], c=[cherry]}
2

the=3 and=2 bat=1 cat=1 hat=1
{a=[apple, avocado], b=[banana, blueberry], c=[cherry]}
2
0

Cost and common mistakes

Counting and indexing are O(n); the sort is O(k log k) for k distinct words.

• map[key] returns null for a missing key. Use getValue if a missing key is a bug.
• A read-only Map is only a read-only view. If someone holds the mutable original, the contents can still change.
• Using a mutable key and changing it after insertion breaks lookups.

Try it yourself

How would you find the most frequent word?

Further reading

• Kotlin documentation (external)
• Kotlin standard library (external)
• Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) (external)