1137. N-th Tribonacci Number - Explanation

Description

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Example 1:

Input: n = 3

Output: 2

Explanation:
T_3 = 0 + 1 + 1 = 2

Example 2:

Input: n = 21

Output: 121415

Constraints:

0 <= n <= 37
The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

Intuition

The tribonacci sequence is defined similarly to Fibonacci, but instead of summing the previous two numbers, we sum the previous three. The base cases are T(0) = 0, T(1) = 1, and T(2) = 1. For any n >= 3, we compute T(n) = T(n-1) + T(n-2) + T(n-3).

A straightforward recursive approach directly implements this definition. However, this leads to exponential time complexity because we recompute the same subproblems many times. Each call branches into three more calls, creating a tree with many redundant calculations.

Algorithm

If n is 0, return 0. If n is 1 or 2, return 1.
Otherwise, recursively compute tribonacci(n-1), tribonacci(n-2), and tribonacci(n-3).
Return the sum of these three values.

class Solution:
    def tribonacci(self, n: int) -> int:
        if n <= 2:
            return 1 if n != 0 else 0
        return self.tribonacci(n - 1) + self.tribonacci(n - 2) + self.tribonacci(n - 3)

Time & Space Complexity

Time complexity: $O(3 ^ n)$
Space complexity: $O(n)$

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution wastes time by recomputing the same values over and over. We can fix this with memoization: store each computed result in a cache. Before computing T(n), check if it already exists in the cache. If so, return the cached value immediately. This transforms our exponential algorithm into a linear one, since each unique subproblem is solved only once.

Algorithm

Create a dp hash map or dictionary to store computed values.
If n is 0, return 0. If n is 1 or 2, return 1.
If n is already in the dp cache, return the cached value.
Otherwise, compute tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3), store it in the dp cache, and return it.

class Solution:
    def __init__(self):
        self.dp = {}

    def tribonacci(self, n: int) -> int:
        if n <= 2:
            return 1 if n != 0 else 0
        if n in self.dp:
            return self.dp[n]

        self.dp[n] = self.tribonacci(n - 1) + self.tribonacci(n - 2) + self.tribonacci(n - 3)
        return self.dp[n]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of working backwards from n and relying on recursion, we can build up the solution from the base cases. Start with the known values T(0), T(1), and T(2), then iteratively compute each subsequent value until we reach T(n). This eliminates recursion overhead and makes the computation straightforward.

Algorithm

If n is 0, return 0. If n is 1 or 2, return 1.
Create an array dp of size n+1 and initialize dp[0] = 0, dp[1] = 1, dp[2] = 1.
For each i from 3 to n, compute dp[i] = dp[i-1] + dp[i-2] + dp[i-3].
Return dp[n].

class Solution:
    def tribonacci(self, n: int) -> int:
        if n <= 2:
            return 1 if n != 0 else 0

        dp = [0] * (n + 1)
        dp[1] = dp[2] = 1
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
        return dp[n]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Dynamic Programming (Space Optimized)

Intuition

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.

Algorithm

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

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]

Time & Space Complexity

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

Common Pitfalls

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.