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

Data Structures and Algorithms, Part 1: Start Here and Learn to Think in Cost

Before any list, tree or graph, you need two skills: knowing roughly how expensive a piece of code is, and having a repeatable way to attack a problem. This first part gives you both, with small programs you can run and change.

1. What this series is, and who it is for

A data structure is a way of arranging data in memory so some jobs become easy. An algorithm is a recipe of steps that solves a problem. Together they are the toolbox that every program is built from, whether it is a phone app, a game or a database.

This series is a gentle, hands-on guide for computer science students and self-taught programmers who are starting out. It assumes you know the basics of any programming language: variables, if, loops and functions. Everything else is explained in plain words, with a picture, a short Kotlin program, and exercises with tests that you run in the free Kotlin Playground.

Here is the map of the nine parts. Each one stands on its own, but they are written to be read in order.

How to use the code

Every program in the series is complete: copy it or press the green or blue Open in Kotlin Playground button, press Run, and change things to see what happens. The Try it boxes contain tests that print PASS or FAIL; they fail at first on purpose. Nothing is sent anywhere until you click a button.

2. Big-O: counting steps instead of seconds

How fast is a piece of code? Seconds depend on your laptop, the language and what else is running. Computer scientists count something steadier: how many basic steps the work takes as the input grows. We call the input size n.

Big-O notation keeps only the part that matters when n gets large. It drops constants and smaller terms, because 3n + 10 and n grow the same way: in a straight line. We write that as O(n), read “order n”.

Reading Big-O from code

• A statement that runs once is O(1).
• A loop over n items is O(n).
• A loop inside a loop, both over n, is O(n²).
• A loop that halves the problem each time is O(log n).
• Steps one after another add; steps inside steps multiply. Then keep the biggest term.

fun constant(n: Int): Int {
    var steps = 0
    steps++                      // one thing, however big n is
    return steps
}

fun linear(n: Int): Int {
    var steps = 0
    for (i in 1..n) steps++      // n things
    return steps
}

fun quadratic(n: Int): Int {
    var steps = 0
    for (i in 1..n) for (j in 1..n) steps++   // n * n things
    return steps
}

fun logarithmic(n: Int): Int {
    var steps = 0
    var x = n
    while (x > 1) { x /= 2; steps++ }          // halve until one is left
    return steps
}

fun main() {
    println("n      O(1)  O(log n)  O(n)    O(n^2)")
    for (n in listOf(10, 100, 1000, 10000)) {
        println("%-6d %-5d %-9d %-7d %d".format(n, constant(n), logarithmic(n), linear(n), quadratic(n)))
    }
}

Look at the last row. At n = 10,000 the linear code takes ten thousand steps and the quadratic code takes a hundred million. That gap is why we care.

3. Time and space

Code costs two things: time (steps) and space (extra memory). Big-O describes both. A loop that only keeps a counter uses O(1) extra space. A program that builds a copy of its input uses O(n).

The two often trade against each other. A common deal is to spend memory to save time: keep a lookup table so you never repeat work. You will see this again and again, in hash maps (Part 2) and dynamic programming (Part 7).

// Does the list contain a duplicate?

// Slow, small: compare every pair. Time O(n^2), extra space O(1).
fun hasDuplicateSlow(nums: List<Int>): Boolean {
    for (i in nums.indices) for (j in i + 1 until nums.size) {
        if (nums[i] == nums[j]) return true
    }
    return false
}

// Fast, bigger: remember what we have seen. Time O(n), extra space O(n).
fun hasDuplicateFast(nums: List<Int>): Boolean {
    val seen = HashSet<Int>()
    for (x in nums) {
        if (!seen.add(x)) return true   // add returns false if it was already there
    }
    return false
}

fun main() {
    val nums = List(20000) { it }       // 0..19999, no duplicates: the worst case
    var t = System.nanoTime()
    println("slow: ${hasDuplicateSlow(nums)}  in ${(System.nanoTime() - t) / 1_000_000} ms")
    t = System.nanoTime()
    println("fast: ${hasDuplicateFast(nums)}  in ${(System.nanoTime() - t) / 1_000_000} ms")
}

4. The Kotlin toolkit used in this series

All examples use Kotlin because it is short to read and runs in the browser. You do not need to know it well. The ideas carry over to Java, Python, C++ or JavaScript, and each Kotlin type used here has a twin in those languages. This is the whole toolkit:

import java.util.PriorityQueue

fun main() {
    // Array and list
    val arr = intArrayOf(5, 3, 8)
    val list = mutableListOf(5, 3, 8)
    list.add(1)
    println("arr[0]=${arr[0]} list=$list size=${list.size}")

    // Map: count letters
    val counts = HashMap<Char, Int>()
    for (c in "banana") counts[c] = (counts[c] ?: 0) + 1
    println("counts=$counts")

    // Set: unique values
    val unique = hashSetOf(1, 2, 2, 3, 3, 3)
    println("unique=$unique")

    // ArrayDeque works as a stack and as a queue
    val dq = ArrayDeque<Int>()
    dq.addLast(1); dq.addLast(2); dq.addLast(3)
    println("removeLast=${dq.removeLast()} removeFirst=${dq.removeFirst()} left=$dq")

    // Priority queue: smallest comes out first
    val pq = PriorityQueue<Int>()
    pq.add(7); pq.add(2); pq.add(5)
    println("poll=${pq.poll()} then ${pq.poll()}")
}

5. A method for solving any problem

The hardest part of a coding problem is usually not the code, it is starting. Use the same six steps every time. They work on exercises, on assignments and on real bugs.

1. Restate it. Say the problem back in your own words. What goes in? What must come out?
2. Try small examples by hand. Include an empty input, a single item and a tricky case.
3. Write the simple, slow solution first. Brute force is fine. A correct slow answer beats a wrong fast one, and it gives you something to test against.
4. Find the waste. Where do you repeat work? Can a different data structure remove it? (Often the answer is a hash map, a sorted order, or a stack.)
5. Write the better version and run your examples through it.
6. State the cost. Say the time and space in Big-O, out loud.

Here is the method on a small problem. Given a list of numbers and a target, find two numbers that add up to the target.

// Step 3: brute force. Check every pair. O(n^2) time, O(1) space.
fun twoSumSlow(nums: IntArray, target: Int): Pair<Int, Int>? {
    for (i in nums.indices) for (j in i + 1 until nums.size) {
        if (nums[i] + nums[j] == target) return i to j
    }
    return null
}

// Step 4: the waste is searching for the partner again and again.
// Remember each number's position, then ask "have I seen target - x?". O(n) time, O(n) space.
fun twoSumFast(nums: IntArray, target: Int): Pair<Int, Int>? {
    val seenAt = HashMap<Int, Int>()
    for ((i, x) in nums.withIndex()) {
        val need = target - x
        seenAt[need]?.let { return it to i }
        seenAt[x] = i
    }
    return null
}

fun main() {
    val nums = intArrayOf(2, 7, 11, 15)
    println(twoSumSlow(nums, 9))     // (0, 1)
    println(twoSumFast(nums, 9))     // (0, 1)
    println(twoSumFast(nums, 100))   // null
}

Notice the shape of the improvement: we traded a little memory for a big gain in speed. That is the story of most of this series.

6. Practice

Two short exercises. The first rewards a better data structure, the second makes Big-O feel real.

fun containsDuplicate(nums: List<Int>): Boolean {
    TODO("remember what you have seen")
}

fun containsDuplicate(nums: List<Int>): Boolean {
    val seen = HashSet<Int>()
    for (x in nums) if (!seen.add(x)) return true
    return false
}

fun stepsToOne(n: Int): Int {
    TODO("halve n until it is 1, counting the steps")
}

fun stepsToOne(n: Int): Int {
    var x = n
    var steps = 0
    while (x > 1) { x /= 2; steps++ }
    return steps
}

7. Takeaways

• Count steps, not seconds, and describe growth with Big-O.
• Loops multiply, sequences add, halving gives a logarithm.
• Extra memory is often the price of speed.
• Always write the simple version first; it is your test oracle.
• Next up: arrays, strings, hash maps and sets, where the first big speed-ups live.