N-th Tribonacci Number

How it works

Notice that to compute T(n), we only need the three most recent values: T(n-1), T(n-2), and T(n-3). We do not need to store the entire history. By keeping just three variables (or a small fixed-size array), we can reduce space complexity from O(n) to O(1).

A clever trick uses an array of size 3 and the modulo operator. At iteration i, we store the new value at index i % 3, which naturally overwrites the oldest value we no longer need.

Steps

1. Initialize an array t = [0, 1, 1] representing the first three tribonacci numbers.
2. If n < 3, return t[n] directly.
3. For each i from 3 to n, compute t[i % 3] = t[0] + t[1] + t[2].
4. Return t[n % 3].

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Incorrect Base Cases

The tribonacci sequence has three base cases: T(0) = 0, T(1) = 1, and T(2) = 1. A common mistake is treating it like Fibonacci and only handling two base cases, or incorrectly setting T(0) = 1. Always explicitly check for n == 0, n == 1, and n == 2 and return the correct values before entering the main computation loop.

Integer Overflow in Recursive Solution

The naive recursive solution without memoization has exponential time complexity O(3^n), which causes timeout for even moderate values of n. Additionally, without memoization, the same subproblems are computed repeatedly, leading to massive redundant work. Always use memoization or an iterative approach to achieve linear time complexity.

class Solution:
    def tribonacci(self, n: int) -> int:
        t = [0, 1, 1]

        if n < 3:
            return t[n]

        for i in range(3, n + 1):
            t[i % 3] = sum(t)
        return t[n % 3]

class Solution {
public:
    int tribonacci(int n) {
        int t[] = {0, 1, 1};
        if (n < 3) return t[n];

        for (int i = 3; i <= n; ++i) {
            t[i % 3] = t[0] + t[1] + t[2];
        }
        return t[n % 3];
    }
};