Start learning free

LESSON 271 OF 348 · MEMOIZATION

Memoization in Kotlin: Caching Fibonacci with a HashMap

Lesson O(n) Read the full explanation

In this video lesson we will learn about memoization and use it to improve the recursive fibonacci algorithm written in the previous lesson:

Problem - Fibonacci:

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Write a recursive function with memoization that given n, returns F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:

0 <= n <= 30

Note:

Your algorithm should run in O(n) time and use O(n) extra space.

STEP 1 OF 6

Guided

Ctrl + Enter to check

KOTLIN · MEMOIZATION

Memoization in Kotlin, explained

What memoization is

Memoization means remembering the result of a function call so that the same call is never computed twice. The first time the function sees an argument, it does the work and stores the answer in a lookup table, usually a map from argument to result. Every later call with that argument reads the stored answer instead.

It pays off when a recursive function keeps asking the same question. The Fibonacci numbers are the classic case: F(0) = 0, F(1) = 1 and F(n) = F(n - 1) + F(n - 2).

Why plain recursion is slow

The direct recursive version has two calls per step, and those calls overlap heavily. F(5) needs F(4) and F(3); F(4) also needs F(3), and so on. The same values are computed over and over, and the number of calls grows exponentially. Counting the calls of a plain recursive F(30) gives 2,692,537, all to produce the number 832,040.

With a shared cache, each value of n from 2 to 30 is computed once. The same F(30) then takes 59 calls: 29 that compute a value, and the rest finding the answer already stored or hitting a base case. That is the difference the lesson's complexity note asks for: O(n) time instead of exponential.

The exercise

The task is to write a recursive fibonacci that uses memoization. The constraints are 0 <= n <= 30, O(n) time and O(n) extra space. The starting code already creates the cache, a HashMap<Int, Int>, inside fibonacci. Because the recursion needs to hand that same map to every call, the work goes into a helper named fib that takes the cache as a parameter.

For example, n = 2 gives 1, n = 3 gives 2 and n = 4 gives 3.

Step by step

Declare the helper fib(n: Int, cache: HashMap<Int, Int>): Int. Passing the map in means every recursive call shares one table.
Handle the base case. For n < 2 the answer is n itself, because F(0) = 0 and F(1) = 1. This is also what stops the recursion.
Check the cache. If it does not contain the key n yet, the value has to be computed.
Compute and store it. Inside that check, set cache[n] to fib(n - 1, cache) + fib(n - 2, cache). The recursive calls fill in the smaller entries on the way.
Return the stored value. After the check, the key is guaranteed to be present, whether it was there from the start or was just added.
Call the helper from fibonacci with the cache it created.

The solution in Kotlin

class Solution {
    fun fib(n: Int, cache: HashMap<Int, Int>): Int {
        if (n < 2) {
            return n
        }
        if (!cache.containsKey(n)) {
            cache[n] = fib(n - 1, cache) + fib(n - 2, cache)
        }
        return cache[n]!!
    }
    fun fibonacci(n: Int): Int {
        val cache = HashMap<Int, Int>()
        return fib(n, cache)
    }
}

The Kotlin details worth knowing:

cache[n] = value is shorthand for cache.set(n, value), and cache[n] alone calls get. Square brackets work on any map.
Reading a map gives a nullable type. cache[n] has the type Int?, because a missing key gives null. The !! operator asserts that the value is not null and turns it into an Int; here that is safe, since the if above has just guaranteed the key exists. If a key were missing, !! would throw a NullPointerException.
The cache is a val. val fixes which map the variable refers to, not the map's contents. A HashMap can still be modified through it.
Base cases stay out of the cache. Returning early for n < 2 keeps the map free of entries it never needs.
Integer size. The values are Int, which is 32 bits. F(46) is 1836311903 and still fits, but F(47) overflows silently to a negative number. The lesson's limit of 30 stays far below that.
A shorter form exists. getOrPut(n) { ... } on a map returns the stored value or computes, stores and returns it. This lesson spells out the check so each step is visible.

Complexity

Time: O(n). Each value from 2 to n is computed once, and each computation does one addition and two calls that are either lookups or already-cached results. Map operations take constant time on average.

Space: O(n). The cache holds up to n - 1 entries, and the recursion goes n calls deep before the first value is stored, so the call stack is also O(n).

Edge cases and common mistakes

n = 0 and n = 1. Both return n from the base case without touching the map.
Creating a new cache inside fib. If each call made its own map, nothing would be shared and the function would be as slow as plain recursion. The map is created once in fibonacci and passed down.
Forgetting to store. Computing fib(n - 1, cache) + fib(n - 2, cache) without writing it into cache[n] gives the right answers but no speed-up.
Dropping the !!. Returning cache[n] directly does not compile, because the function promises an Int and the expression is an Int?.
Skipping the base case. Without n < 2, the recursion would reach fib(-1, cache) and never stop, ending in a StackOverflowError.

Key takeaways

Memoization stores each answer the first time it is computed and reuses it afterwards.
It turns the exponential Fibonacci recursion into O(n) work, because there are only n + 1 different questions.
Share one table across all recursive calls by creating it once and passing it as a parameter.
In Kotlin, a map lookup returns a nullable value, so use !! only when you have just ensured the key is present.

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

Start learning free