Data Structures, Algorithms and Programming Patterns · Part 2 of 9

Data Structures and Algorithms, Part 2: Arrays, Strings, Hash Maps and Sets

Arrays, strings, hash maps and hash sets cover most of what everyday programs store. This part shows how each one works inside, what every operation costs, and how a hash map can turn a slow search into a single step.

1. Arrays: numbered boxes in a row

An array is a row of boxes of the same size, sitting side by side in memory, each holding one value. Every box has a number called its index, and counting starts at 0.

That formula is the reason for the array's best trick: reading or writing arr[i] costs O(1). It does not matter whether the array has ten boxes or ten million.

The price is that the boxes are packed tightly. To put a new value in the middle, every value after it has to shuffle one box to the right to make room. To remove one, they shuffle left to close the gap.

fun insertAt(arr: IntArray, size: Int, index: Int, value: Int): Int {
    var moves = 0
    for (i in size downTo index + 1) {   // walk from the back so we do not overwrite anything
        arr[i] = arr[i - 1]
        moves++
    }
    arr[index] = value
    return moves
}

fun main() {
    val a = IntArray(6)
    a[0] = 10; a[1] = 20; a[2] = 30; a[3] = 40   // size 4, two spare boxes
    println("a[2] = ${a[2]}")                      // O(1): jump straight to box 2

    val moves = insertAt(a, 4, 1, 15)
    println(a.joinToString() + "   moves=$moves")  // three values had to shift

    val appendMoves = insertAt(a, 5, 5, 99)        // at the end
    println(a.joinToString() + "   moves=$appendMoves")

    // The same effect with a MutableList: add(index, value) shifts for you.
    val big = MutableList(1000) { it }
    big.add(0, -1)                                 // every one of the 1000 items moves
    println("first=${big[0]} second=${big[1]} size=${big.size}")
}

Fixed size

A plain array has a size you choose when you create it, and it cannot grow. In Kotlin, IntArray(5) makes five zeros and intArrayOf(1, 2, 3) makes an array with those values. Asking for arr[5] in a five-box array throws an IndexOutOfBoundsException, which is the computer saying “that box does not exist”.

2. Growable lists and the idea of amortised cost

Most of the time you do not know the size in advance. A growable list (Kotlin's MutableList, backed by ArrayList; Python's list; Java's ArrayList) hides a plain array and grows it for you.

It keeps a hidden array that is usually bigger than needed. The number of boxes is its capacity; the number actually used is its size. When you add an item and the array is full, the list allocates a new array about twice as big, copies everything across, and carries on.

So is add O(1) or O(n)? One unlucky add costs O(n) because of the copy. But look at many adds together. Doubling means the total copying over n adds is about 1 + 2 + 4 + … + n, which is less than 2n. Spread over n adds, that is about two copies per add. We say add is amortised O(1): on average over a long run it is constant, even though a single call can be slow.

class TinyList {
    private var data = IntArray(1)
    var size = 0
        private set
    var copies = 0
        private set

    fun add(x: Int) {
        if (size == data.size) {                    // full: grow to double
            val bigger = IntArray(data.size * 2)
            for (i in 0 until size) { bigger[i] = data[i]; copies++ }
            data = bigger
        }
        data[size] = x
        size++
    }

    operator fun get(i: Int): Int {
        if (i !in 0 until size) throw IndexOutOfBoundsException("index $i, size $size")
        return data[i]
    }
}

fun main() {
    for (n in listOf(10, 1000, 100000)) {
        val list = TinyList()
        for (i in 1..n) list.add(i)
        val perAdd = list.copies.toDouble() / list.size
        println("n=$n copies=${list.copies} copies per add=${"%.2f".format(perAdd)}")
    }
}

What costs what in a list

3. Strings: arrays of characters with rules

A string is a sequence of characters, and you can think of it as an array of Char. So s[i] is O(1) and s.length is O(1). Most things you do to the whole string, such as searching or comparing, are O(n) because they look at the characters.

Strings never change

In Kotlin, Java and Python a string is immutable: once created, it cannot be edited. Methods like uppercase() or replace() do not change the string, they build a new one. That is safe, because nobody can change a string under your feet, but it has a cost.

Consider building a long string with result = result + "x" in a loop. Each + creates a brand new string and copies everything so far. Copy 1 character, then 2, then 3, up to n: that is about n² / 2 copies in total, so O(n²). The fix is a StringBuilder: a growable buffer, just like the growable list, so appending is amortised O(1) and the whole build is O(n).

fun main() {
    val s = "hello world"
    val shout = s.uppercase()
    println("$s -> $shout")                 // s itself did not change

    println(s[4])                           // 'o', O(1)
    println(s.substring(0, 5))              // hello
    println(s.indexOf("world"))             // 6
    println(s.contains("lo w"))             // true
    println(s.split(" "))                   // [hello, world]
    println(s.reversed())                   // dlrow olleh
    println(s.replace('o', '0'))            // hell0 w0rld

    // Build a string piece by piece with StringBuilder: O(n) overall.
    val sb = StringBuilder()
    for (i in 1..5) sb.append(i).append(',')
    sb.setLength(sb.length - 1)             // drop the last comma
    println(sb.toString())                  // 1,2,3,4,5

    // Strings are sequences of Char, and Char is a number underneath.
    println('a'.code)                       // 97
    println('c' - 'a')                      // 2, the position of c in the alphabet
    println('7'.isDigit())                  // true
    println('Q'.lowercaseChar())            // q
}

Counting characters

Many string problems come down to how many of each letter are there? If the text only has lowercase letters a to z, you do not need a map. Use an array of 26 counters and turn a letter into an index with c - 'a'.

Palindromes and anagrams

A palindrome reads the same forwards and backwards, like “level”. A neat way to check it is with two pointers: one starts at the left end, one at the right end, and they walk toward each other comparing characters. Two strings are anagrams if they use exactly the same letters the same number of times, like “listen” and “silent”. If you count the letters of both, the counts must match.

fun isPalindrome(s: String): Boolean {
    var left = 0
    var right = s.length - 1
    while (left < right) {
        if (s[left] != s[right]) return false
        left++
        right--
    }
    return true            // O(n) time, O(1) extra space
}

fun letterCounts(word: String): IntArray {
    val counts = IntArray(26)
    for (c in word) counts[c - 'a']++
    return counts
}

fun sameLetters(a: String, b: String): Boolean =
    letterCounts(a).contentEquals(letterCounts(b))     // O(n) time, O(1) space (26 never grows)

fun main() {
    println(isPalindrome("level"))      // true
    println(isPalindrome("levels"))     // false
    println(isPalindrome(""))           // true, nothing to disagree
    println(sameLetters("listen", "silent"))   // true
    println(sameLetters("rat", "car"))         // false
    println(letterCounts("banana").take(14))    // counts for a..n
}

4. Hashing: finding things without searching

Arrays give you instant access by position. But often you want access by meaning: the price of “apple”, the user named “sara”, whether the number 42 has appeared already. Searching a list for those is O(n). A hash table makes it O(1) on average.

The rule is a hash function: it turns any key (a string, a number, an object) into an integer called a hash code. The table has a row of numbered slots called buckets. The bucket for a key is the hash code reduced to a valid bucket number, usually with a remainder: hashCode % bucketCount.

Collisions

There are far more possible keys than buckets, so two different keys sometimes land in the same bucket. This is called a collision, and it is normal. The simplest fix, used above, is chaining: each bucket holds a small list of the entries that landed there. To look up a key, jump to its bucket and check the few entries inside, comparing with equals.

If the hash function spreads keys evenly and the table has enough buckets, every chain stays tiny and a lookup is a couple of steps. When the table gets too full, real implementations resize: they make more buckets and re-place every entry, the same trick the growable list uses. That keeps the average cost O(1).

class MiniHashSet(private val bucketCount: Int = 8) {
    private val buckets = Array(bucketCount) { mutableListOf<String>() }

    fun bucketOf(key: String): Int = Math.floorMod(key.hashCode(), bucketCount)

    fun add(key: String): Boolean {
        val chain = buckets[bucketOf(key)]
        if (key in chain) return false      // already there
        chain.add(key)
        return true
    }

    fun contains(key: String): Boolean = key in buckets[bucketOf(key)]

    fun show() {
        for ((i, chain) in buckets.withIndex()) println("bucket $i: $chain")
    }
}

fun main() {
    val set = MiniHashSet()
    val words = listOf("cat", "dog", "bird", "fish", "cow", "ant", "bee", "cat")
    for (w in words) {
        val added = set.add(w)
        println("%-5s hashCode=%-9d bucket=%d added=%s".format(w, w.hashCode(), set.bucketOf(w), added))
    }
    println()
    set.show()
    println()
    println("contains dog? ${set.contains("dog")}")
    println("contains emu? ${set.contains("emu")}")
}

Why only the average is O(1)

In the worst case every key collides into one bucket and the table degrades into a single long list: O(n). A good hash function and resizing make that practically never happen, so we say average O(1). This is also why a hash table gives up order: keys are placed by their hash code, not by when you added them or how they compare, so iterating a plain hash table gives no meaningful order.

5. HashMap, HashSet and their relatives

Two structures are built on a hash table.

• A hash set stores unique keys and answers “is it in there?” in O(1) on average.
• A hash map (a dictionary) stores key-value pairs: look up a key, get its value. Keys are unique; values can repeat.

A set is really a map where you only care about the keys. In Kotlin, mapOf, mutableMapOf and HashMap are the usual map types, and setOf, mutableSetOf and HashSet the usual sets.

Four flavours and what order means

Sometimes you do need order. The standard library offers variations that differ in what order they keep and what that costs.

A TreeMap keeps its keys sorted using a balanced tree (you will build such trees in Part 4). That costs O(log n) per operation instead of O(1), but it unlocks questions a hash table cannot answer cheaply: the smallest key, the largest, or the closest key to a given value.

import java.util.TreeMap

fun countWords(words: List<String>, into: MutableMap<String, Int>) {
    for (w in words) into[w] = (into[w] ?: 0) + 1
}

fun main() {
    val words = listOf("pear", "apple", "fig", "banana", "apple", "fig", "apple")

    val hash = HashMap<String, Int>()
    val linked = LinkedHashMap<String, Int>()
    val tree = TreeMap<String, Int>()
    countWords(words, hash)
    countWords(words, linked)
    countWords(words, tree)

    println("HashMap       $hash")      // same pairs, order not meaningful
    println("LinkedHashMap $linked")    // first-seen order: pear, apple, fig, banana
    println("TreeMap       $tree")      // alphabetical

    println(linked["apple"])            // 3
    println(linked["kiwi"])             // null, missing key
    println(linked.getOrDefault("kiwi", 0))   // 0

    println(tree.firstKey())            // apple
    println(tree.lastKey())             // pear
    println(tree.ceilingKey("b"))       // banana, smallest key at or after "b"
    println(tree.floorKey("c"))         // banana, largest key at or before "c"

    val seen = LinkedHashSet<Int>()
    for (x in listOf(3, 1, 3, 2, 1)) seen.add(x)
    println(seen)                       // [3, 1, 2]: duplicates gone, first-seen order kept
}

Your own classes as keys

A hash table needs two things from a key: hashCode() to pick the bucket, and equals() to confirm a match inside the bucket. Strings and numbers have both built in. For your own class, Kotlin's data class writes both for you, based on the fields in the constructor. A plain class does not: two separate objects count as different even when all their fields match.

data class Point(val x: Int, val y: Int)

class Cell(val x: Int, val y: Int)       // plain class: no equals, no hashCode

fun main() {
    val visited = HashSet<Point>()
    visited.add(Point(1, 2))
    println(Point(1, 2) in visited)                              // true: same fields, equal
    println(Point(1, 2).hashCode() == Point(1, 2).hashCode())    // true

    val plain = HashSet<Cell>()
    plain.add(Cell(1, 2))
    println(Cell(1, 2) in plain)                                 // false: a different object

    val names = HashMap<Point, String>()
    names[Point(0, 0)] = "origin"
    names[Point(3, 4)] = "far"
    println(names[Point(0, 0)])          // origin
    println(names[Point(9, 9)])          // null
}

6. Counting and grouping with maps

Two jobs show up everywhere, and both are one loop over a map.

• Frequency counting: how many times does each thing occur? Map from item to count.
• Grouping: collect items that share a property. Map from the property (the key) to a list of items.

The counting pattern is always “read the old count, or zero if missing, and add one”. Kotlin gives shortcuts so you do not write it by hand: groupingBy { }.eachCount() to count, groupBy { } to group, and getOrPut to create a list the first time a key appears.

fun groupAnagrams(words: List<String>): List<List<String>> {
    val groups = HashMap<String, MutableList<String>>()
    for (w in words) {
        val key = w.toCharArray().sorted().joinToString("")   // "eat" -> "aet"
        groups.getOrPut(key) { mutableListOf() }.add(w)
    }
    return groups.values.toList()
}

fun main() {
    val words = "to be or not to be".split(" ")

    // Counting by hand
    val counts = HashMap<String, Int>()
    for (w in words) counts[w] = (counts[w] ?: 0) + 1
    println(counts.toSortedMap())

    // Counting with the shortcut
    println(words.groupingBy { it }.eachCount().toSortedMap())

    // Grouping by a property: here, word length
    println(words.groupBy { it.length })

    // Most common word
    val best = counts.maxByOrNull { it.value }
    println("most common: ${best?.key} x${best?.value}")

    // Grouping anagrams, O(n * k log k) for n words of length k
    val groups = groupAnagrams(listOf("eat", "tea", "tan", "ate", "nat", "bat"))
    println(groups.sortedBy { it.first() })
}

The cost of counting is O(n) time for n items and O(k) extra space, where k is the number of different items. For grouping anagrams, building each key sorts a word of length k, which costs O(k log k), so the total is O(n * k log k).

7. Worked problems: from slow to fast

Time to use the six-step method from Part 1. In each problem the slow version is the one you would write first, and a set or map removes the repeated searching.

Problem A: common items

Given two lists, which values appear in both? The slow way takes each item of the first list and scans the second one: O(n * m). The waste is the scanning. Put one list into a hash set, and each check becomes O(1), so the whole job is O(n + m).

Problem B: the first repeat

Return the first value that appears a second time as you read left to right. Keep a set of values seen so far. The first time add says “already there”, you have your answer. One pass, O(n).

fun commonSlow(a: List<Int>, b: List<Int>): List<Int> {
    val result = mutableListOf<Int>()
    for (x in a) if (x in b && x !in result) result.add(x)   // x in b scans b: O(n * m)
    return result
}

fun commonFast(a: List<Int>, b: List<Int>): List<Int> {
    val inB = b.toHashSet()                     // O(m)
    val result = LinkedHashSet<Int>()           // unique, keeps order
    for (x in a) if (x in inB) result.add(x)    // each check is O(1)
    return result.toList()
}

fun firstRepeat(nums: List<Int>): Int? {
    val seen = HashSet<Int>()
    for (x in nums) {
        if (!seen.add(x)) return x
    }
    return null
}

fun main() {
    val a = listOf(4, 9, 5, 9, 4)
    val b = listOf(9, 4, 9, 8, 4)
    println(commonSlow(a, b))     // [4, 9]
    println(commonFast(a, b))     // [4, 9]
    println(firstRepeat(listOf(2, 5, 1, 2, 3, 5, 1)))   // 2
    println(firstRepeat(listOf(1, 2, 3)))               // null
}

Problem C: the longest run of consecutive numbers

Given unsorted numbers, find the length of the longest run of values that follow each other, like 1, 2, 3, 4. The numbers do not need to be next to each other in the input.

Sorting gives O(n log n), which is fine, but a set does it in O(n). The key idea: only start counting at the beginning of a run. A number x is the beginning of a run if x - 1 is not in the set. From each beginning, walk up x+1, x+2, ... while the numbers are in the set.

You will write this one yourself in the practice section. Before that, one more kind of data: tables of numbers.

8. Two-dimensional arrays and grids

A matrix or grid is an array of arrays: rows, each holding columns. You write grid[row][col]. Grids model spreadsheets, game boards, images (a grid of pixels) and maps.

Visiting every cell takes two nested loops, so a grid with R rows and C columns costs O(R * C). That is linear in the number of cells, not quadratic in anything, so name your sizes carefully when you state the cost.

Looking at neighbours

A common task is “what is next to this cell?”. Instead of four copy-pasted if blocks, store the four moves in two small arrays of row and column offsets, loop over them, and check the new position is inside the grid before reading it.

fun main() {
    val grid = arrayOf(
        intArrayOf(1, 2, 3),
        intArrayOf(4, 5, 6),
        intArrayOf(7, 8, 9),
    )
    val rows = grid.size
    val cols = grid[0].size

    // Row by row: the natural, fast order for arrays.
    for (r in 0 until rows) println(grid[r].joinToString(" "))

    // Column sums: swap the loop order.
    for (c in 0 until cols) {
        var sum = 0
        for (r in 0 until rows) sum += grid[r][c]
        println("column $c sum = $sum")
    }

    // Neighbours with direction arrays, skipping cells outside the grid.
    val dr = intArrayOf(-1, 1, 0, 0)
    val dc = intArrayOf(0, 0, -1, 1)
    fun neighbours(r: Int, c: Int): List<Int> {
        val result = mutableListOf<Int>()
        for (k in 0 until 4) {
            val nr = r + dr[k]
            val nc = c + dc[k]
            if (nr in 0 until rows && nc in 0 until cols) result.add(grid[nr][nc])
        }
        return result
    }
    println(neighbours(1, 1))    // [2, 8, 4, 6] all four exist
    println(neighbours(0, 0))    // [4, 2] corner: only two exist

    // Transpose: cell (r, c) moves to (c, r). Rows become columns.
    val t = Array(cols) { c -> IntArray(rows) { r -> grid[r][c] } }
    for (row in t) println(row.joinToString(" "))
}

9. The cost table

Here is everything from this part on one page. Keep it nearby; choosing a structure is mostly looking up the operation you do most often.

Choosing quickly

• You index by position or loop over everything: array or list.
• You ask “have I seen this?” or “what is the value for this key?”: hash set or hash map.
• You also want the keys in sorted order or nearby keys: TreeMap or TreeSet.
• You want a predictable order without sorting: LinkedHashMap or LinkedHashSet.
• Strings: use StringBuilder when you build one from many pieces.

10. Practice

Five exercises, from a warm-up with two pointers to one that rewards a hash set. Each has edge cases (empty, single item, duplicates) and some have large inputs, so a version with a nested loop will be very slow.

fun isPalindrome(s: String): Boolean {
    TODO("move two pointers inward, skipping characters that are not letters or digits")
}

fun isPalindrome(s: String): Boolean {
    var left = 0
    var right = s.length - 1
    while (left < right) {
        if (!s[left].isLetterOrDigit()) { left++; continue }
        if (!s[right].isLetterOrDigit()) { right--; continue }
        if (s[left].lowercaseChar() != s[right].lowercaseChar()) return false
        left++
        right--
    }
    return true
}

fun isAnagram(a: String, b: String): Boolean {
    TODO("count the characters of a, then use up the counts with b")
}

fun isAnagram(a: String, b: String): Boolean {
    if (a.length != b.length) return false
    val counts = HashMap<Char, Int>()
    for (c in a) counts[c] = (counts[c] ?: 0) + 1
    for (c in b) {
        val left = (counts[c] ?: 0) - 1
        if (left < 0) return false
        counts[c] = left
    }
    return true
}

fun firstUniqueChar(s: String): Int {
    TODO("count every character, then scan again for the first with count 1")
}

fun firstUniqueChar(s: String): Int {
    val counts = HashMap<Char, Int>()
    for (c in s) counts[c] = (counts[c] ?: 0) + 1
    for ((i, c) in s.withIndex()) {
        if (counts[c] == 1) return i
    }
    return -1
}

fun longestConsecutive(nums: List<Int>): Int {
    TODO("put the numbers in a set, and count upward from the start of each run")
}

fun longestConsecutive(nums: List<Int>): Int {
    val set = nums.toHashSet()
    var best = 0
    for (x in set) {
        if ((x - 1) in set) continue          // not the start of a run
        var length = 1
        while ((x + length) in set) length++
        if (length > best) best = length
    }
    return best
}

fun rotateClockwise(m: List<List<Int>>): List<List<Int>> {
    TODO("build the new grid with cols rows and rows columns")
}

fun rotateClockwise(m: List<List<Int>>): List<List<Int>> {
    if (m.isEmpty()) return emptyList()
    val rows = m.size
    val cols = m[0].size
    return List(cols) { r -> List(rows) { c -> m[rows - 1 - c][r] } }
}

11. Takeaways

• Position is cheap in arrays; searching by value is cheap in hash tables.
• Middle inserts and deletes in arrays cost O(n); appends are amortised O(1).
• Never build a long string with repeated +; use StringBuilder.
• A hash map or set is the first tool to reach for when you notice repeated searching.
• Counting and grouping are one-pass jobs with a map: count with eachCount, group with groupBy.
• Pick the map type by the order you need: none, insertion, or sorted.
• Next up: stacks, queues and linked lists, where the order of arrival decides what comes out first.