LESSON 186 OF 414 · LOOPS - CHALLENGES

Tribonacci in Scala: O(n) Time and O(1) Space with a Loop

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

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

Given n, calculate and return T(n).

Example 1:

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

Example 2:

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

Example 3:

Input: n = 5
Output: 7
Explanation: T(5) = T(4) + T(3) + T(2) = 4 + 2 + 1 = 7.

Note:

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

STEP 1 OF 8

Guided

Ctrl + Enter to check

SCALA · LOOPS - CHALLENGES

Tribonacci in Scala, explained

Problem overview

The method tribonacci takes an Int named n and returns T(n), the n-th Tribonacci number. The sequence starts with T(0) = 0, T(1) = 1 and T(2) = 1. After that, every number is the sum of the three before it: T(n) = T(n - 1) + T(n - 2) + T(n - 3).

For n = 4, the answer is T(3) + T(2) + T(1). Since T(3) = 1 + 1 + 0 = 2, that gives 2 + 1 + 1 = 4. The first terms are 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149.

Approach: keep only the last three values

The definition reads like a recursive function, and a direct translation works for small inputs. But each call spawns three more, and the same values are recomputed again and again, so the running time grows exponentially.

The statement asks for O(n) time and O(1) space. The key observation is that computing the next number needs only the three most recent ones. There is no reason to remember T(3) once you have reached T(7). So the loop carries three variables, computes one new number per iteration, and shifts the window forward by one position.

Step by step

Handle the base cases. T(0) and T(1) equal their own index, so when n is less than 2, return n right away.
Declare the window. prev2, prev and curr start as T(0), T(1) and T(2). They are vars because every iteration changes them. curr is the newest value, prev is one step behind and prev2 two steps.
Loop from 3 to n. Each iteration produces one new term, T(3) through T(n). For n = 2 the loop does nothing, and curr, which already holds T(2), is the answer.
Compute the next term as the sum of the three variables. It is a val because it is a new value in every pass and never reassigned.
Shift the window, oldest first. Copy prev into prev2, then curr into prev, then next into curr. Each variable is overwritten only after its old value has been copied one place back. In the wrong order, a value would be lost before anyone used it.
Return curr. After the last iteration it holds T(n).

The solution in Scala

class Solution {
    def tribonacci(n: Int): Int = {
        if (n < 2) {
            return n
        }
        var prev2 = 0
        var prev = 1
        var curr = 1
        for (i <- 3 to n) {
            val next = prev2 + prev + curr
            prev2 = prev
            prev = curr
            curr = next
        }
        return curr
    }
}

The Scala details worth knowing:

3 to n is inclusive. It includes both 3 and n. When n is 2, 3 to 2 is an empty range, so the body never runs. 3 until n would stop one term early.
for (i <- ...) is a generator. The loop variable i is a fresh val in each pass. Here it only counts iterations, and the body never reads it.
val versus var. A val can't be reassigned; a var can. Using val for next and var for the three window variables tells the reader which names change over time.
return is optional. The last expression of a block is its value, so the final line could be just curr. Scala programmers usually write that. The explicit return in the lesson works the same way. A method that uses return needs its result type written out, which : Int does here.
Int is 32 bits. Scala does not warn when a sum goes past the limit; the value silently wraps around. This matters for large n, as described below.

A worked trace

Take n = 5. Before the loop, prev2, prev and curr are 0, 1 and 1.

i = 3: next is 0 + 1 + 1 = 2, and the window becomes 1, 1, 2.
i = 4: next is 1 + 1 + 2 = 4, and the window becomes 1, 2, 4.
i = 5: next is 1 + 2 + 4 = 7, and the window becomes 2, 4, 7.

The loop ends, and curr is 7, which is T(5). The oldest value drops out of the window on every pass, which is why three variables are enough no matter how large n is.

Complexity

Time: O(n). The loop runs n - 2 times and each pass does a fixed number of additions and assignments.

Space: O(1). The method uses four local variables whatever the size of n. A recursive version would need a call stack as deep as n, and a memoised one would store n values.

Edge cases and common mistakes

Small n. tribonacci(0) returns 0, tribonacci(1) returns 1 and tribonacci(2) returns 1. The last one comes from the initial value of curr with an empty loop.
Overflow. T(37) is 2082876103, the largest term that fits in an Int. tribonacci(38) returns -463960867, because the true value is above 2147483647 and the addition wraps. If larger inputs mattered, the variables and the return type would be Long, which holds terms up to a much larger n.
Shifting in the wrong order. If curr = next comes first, then prev = curr copies the new value and the window collapses into duplicates.
Using until. for (i <- 3 until n) computes only up to T(n - 1), so every answer is one term short.
Off-by-one starting values. The variables must start at T(0), T(1) and T(2). Starting curr at 0 shifts the whole sequence.

Testing

n = 3 gives 2.
n = 4 gives 4.
n = 5 gives 7.
n = 10 gives 149.
n = 0 gives 0, and n = 2 gives 1.

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

Start learning free