Start learning free

LESSON 183 OF 410 · LOOPS - CHALLENGES

Tribonacci in Python: O(n) Time and O(1) Space

Practice Read the full explanation

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
    Ctrl + Enter to check

    PYTHON · LOOPS - CHALLENGES

    Tribonacci in Python, explained

    Problem overview

    The Tribonacci sequence works like Fibonacci, but each number is the sum of the three numbers before it. It starts with T(0) = 0, T(1) = 1 and T(2) = 1, and for larger n, T(n) = T(n - 1) + T(n - 2) + T(n - 3). The method tribonacci receives n and returns T(n).

    The first terms are 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149. For example, T(3) = 1 + 1 + 0 = 2, T(4) = 2 + 1 + 1 = 4 and T(5) = 4 + 2 + 1 = 7.

    The statement asks for O(n) time and O(1) space.

    Approach: keep only the last three values

    The direct translation of the definition is a recursive function that calls itself three times. It is short, but it recomputes the same values again and again, and its running time grows exponentially. Storing every term in a list or a memo table fixes the time, but it keeps O(n) numbers in memory and a recursive version also hits Python's recursion limit of 1000 calls for large n.

    The better idea is to notice what each new term needs: only the three before it. So three variables are enough. Walk up from T(2) to T(n), and at each step compute the next term and slide the window one place forward, forgetting the oldest value.

    Step by step

    1. Handle n < 2 first. T(0) is 0 and T(1) is 1, so each answer is n itself.
    2. Set up the window. prev2, prev and curr start as T(0), T(1) and T(2), which are 0, 1 and 1. A tuple assignment does it in one line. For n = 2 the loop below does not run, and curr is already the answer.
    3. Loop from 3 to n with range(3, n + 1). The end of range is exclusive, so n + 1 is needed to include n.
    4. Compute next as prev2 + prev + curr, the next term.
    5. Shift the window, oldest first. Assign prev to prev2, then curr to prev, then next to curr. Each variable is overwritten only after its old value has moved one place back.
    6. Return curr. After the last iteration it holds T(n).

    Tracing n = 5

    inextprev2prevcurr
    start011
    32112
    44124
    57247

    The function returns 7, which matches T(5).

    The solution in Python

    class Solution:
    def tribonacci(self, n: int) -> int:
        if n < 2:
            return n
        prev2, prev, curr = 0, 1, 1
        for i in range(3, n + 1):
            next = prev2 + prev + curr
            prev2 = prev
            prev = curr
            curr = next
        return curr

    Python details to notice:

    • Tuple assignment. prev2, prev, curr = 0, 1, 1 evaluates the right side first and then assigns the three names. The same feature can do the whole shift in one line, prev2, prev, curr = prev, curr, next, with no ordering to get wrong.
    • The name next hides a built-in. Python has a function next(). Inside this method the local variable replaces it. That is harmless here, because the method never calls next(), but a name like nxt avoids the problem.
    • The loop variable i is unused. It only counts iterations. _ is the usual name for such a variable.
    • Integers have no size limit. Tribonacci numbers grow fast, roughly by a factor of 1.84 each step. T(38) is 3831006429, which no longer fits in a signed 32-bit integer, and Python keeps going: T(100) is 98079530178586034536500564.

    Complexity

    Time: O(n). The loop runs n - 2 times with a constant amount of work per pass. Strictly, the numbers themselves grow with n, so additions on very large values cost more, but for the sizes in practice this is constant.

    Space: O(1). Four variables are used, whatever n is.

    Edge cases and common mistakes

    • n = 0, 1 and 2. T(0) returns 0 and T(1) returns 1 from the early return. T(2) skips the loop and returns curr, which is 1.
    • Starting at the wrong values. This sequence starts 0, 1, 1. Other sources start with 0, 0, 1 and give a different list, so T(3) would be 1 instead of 2.
    • Shifting in the wrong order. If curr = next comes before prev = curr, the old curr is lost and prev gets the new value. With that mistake tribonacci(5) returns 12 instead of 7.
    • An off-by-one range. range(3, n) stops one term early and returns T(n - 1).
    • Plain recursion. It is correct for small n, but it recomputes values exponentially often. A memoised recursive version with functools.lru_cache is fast, but it raises RecursionError for an input as large as 5000.

    Testing

    • tribonacci(0) returns 0.
    • tribonacci(2) returns 1.
    • tribonacci(3) returns 2.
    • tribonacci(4) returns 4.
    • tribonacci(10) returns 149.
    • tribonacci(37) returns 2082876103.
    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free