N-th Tribonacci Number - Solution & Explanation
Problem Statement
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 = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4
Example 2:
Input: n = 25 Output: 1389537
Constraints:
0 <= n <= 37- The answer is guaranteed to fit within a 32-bit integer, ie.
answer <= 2^31 - 1.
Approach Overview
Problem Overview: The Tribonacci sequence is similar to Fibonacci, but each number is the sum of the previous three values instead of two. You are given an integer n and must return the n-th Tribonacci number where T0 = 0, T1 = 1, T2 = 1, and Tn = T(n-1) + T(n-2) + T(n-3) for n ≥ 3. The task is essentially evaluating this recurrence efficiently.
Approach 1: Recursive Solution with Memoization (Time: O(n), Space: O(n))
The direct recursive definition mirrors the mathematical recurrence: compute T(n-1), T(n-2), and T(n-3) and sum them. Pure recursion recomputes the same values many times, leading to exponential complexity. Memoization fixes that by storing previously computed results in a cache (array or hash map). Each state T(i) is computed once and reused afterward. This approach clearly demonstrates how overlapping subproblems appear in dynamic programming, and it’s a natural way to translate the recurrence into code.
Approach 2: Iterative Dynamic Programming (Time: O(n), Space: O(1))
The recurrence only depends on the previous three values. Instead of storing the entire DP table, you can track just three variables representing T(n-3), T(n-2), and T(n-1). Start from the base cases and iterate from 3 to n, computing the next Tribonacci value as the sum of the three tracked values. After each iteration, shift the variables forward. This reduces space to constant while keeping the same linear runtime. The approach is a classic bottom-up dynamic programming pattern and avoids recursion overhead.
This iterative strategy works because the Tribonacci recurrence forms a simple dependency chain. At step i, all required values have already been computed in earlier iterations. Instead of recursion stacks or large arrays, you only keep the minimal state required to produce the next result.
Recommended for interviews: The iterative dynamic programming approach with three variables is the expected solution. It runs in O(n) time and O(1) space and demonstrates that you understand how to optimize a recurrence relation. Showing the memoized recursion first can help explain the transition from naive recursion to memoization and finally to an iterative DP implementation, which is typically what interviewers want to see.
Approach 1: Iterative Dynamic Programming Approach
This approach uses an iterative method with dynamic programming principles to compute the N-th Tribonacci number. We maintain a list or variables to store previously computed values to avoid redundant calculations. This approach provides an optimal solution both in terms of time and space.
The C solution initializes the three previous values T0, T1, and T2 and iteratively calculates up to the N-th term.
Complexity
Time Complexity: O(n), Space Complexity: O(1).
Approach 2: Recursive Solution with Memoization
This approach employs recursion with memoization to compute the Tribonacci numbers. Here, we recursively break the problem into smaller subproblems and cache the results of each computed Tribonacci number to avoid redundant calculations, thus optimizing the recursive solution in terms of performance.
In this Python code, a dictionary is used as a memoization cache, storing the results of each calculated Tribonacci number.
Complexity
Time Complexity: O(n), Space Complexity: O(n).
Approach 3: Dynamic Programming
According to the recurrence relation given in the problem, we can use dynamic programming to solve it.
We define three variables a, b, c to represent T_{n-3}, T_{n-2}, T_{n-1}, respectively, with initial values of 0, 1, 1.
Then we decrease n to 0, updating the values of a, b, c each time, until n is 0, at which point the answer is a.
The time complexity is O(n), and the space complexity is O(1). Here, n is the given integer.
Code
Python
Java
C++
Go
TypeScript
JavaScript
PHP
Approach 4: Matrix Exponentiation to Accelerate Recurrence
We define Tib(n) as a 1 times 3 matrix \begin{bmatrix} T_n & T_{n - 1} & T_{n - 2} \end{bmatrix}, where T_n, T_{n - 1} and T_{n - 2} represent the nth, (n - 1)th and (n - 2)th Tribonacci numbers, respectively.
We hope to derive Tib(n) from Tib(n-1) = \begin{bmatrix} T_{n - 1} & T_{n - 2} & T_{n - 3} \end{bmatrix}. That is, we need a matrix base such that Tib(n - 1) times base = Tib(n), i.e.,
$
\begin{bmatrix}
T_{n - 1} & T_{n - 2} & T_{n - 3}
\end{bmatrix} times base = \begin{bmatrix} T_n & T_{n - 1} & T_{n - 2} \end{bmatrix}
Since T_n = T_{n - 1} + T_{n - 2} + T_{n - 3}, the matrix base is:
\begin{bmatrix}
1 & 1 & 0 \
1 & 0 & 1 \
1 & 0 & 0
\end{bmatrix}
We define the initial matrix res = \begin{bmatrix} 1 & 1 & 0 \end{bmatrix}, then T_n is equal to the sum of all elements in the result matrix of res multiplied by base^{n - 3}. This can be solved using matrix exponentiation.
The time complexity is O(log n), and the space complexity is O(1)$.
Code
Python
Java
C++
Go
TypeScript
JavaScript
PHP
Complexity Comparison
| Approach | Complexity |
|---|---|
| Iterative Dynamic Programming Approach | Time Complexity: O(n), Space Complexity: O(1). |
| Recursive Solution with Memoization | Time Complexity: O(n), Space Complexity: O(n). |
| Dynamic Programming | — |
| Matrix Exponentiation to Accelerate Recurrence | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n) | O(n) | Good for understanding the recurrence and demonstrating memoization in interviews |
| Dynamic Programming (Array) | O(n) | O(n) | Useful when storing the entire sequence for later access |
| Iterative DP (Space Optimized) | O(n) | O(1) | Best choice for interviews and production code due to minimal memory usage |
Video Solution
N-th Tribonacci Number - Leetcode 1137 • NeetCodeIO • 14,623 views views
Watch 9 more video solutions →Frequently Asked Questions
Is N-th Tribonacci Number easy or hard?
N-th Tribonacci Number Python/Java solution
How to solve N-th Tribonacci Number in O(n)?
What is the best approach for N-th Tribonacci Number?
Is N-th Tribonacci Number asked at Google/Amazon/Meta?
What data structure is used in N-th Tribonacci Number?
What is the time complexity of N-th Tribonacci Number?
Ready to solve this problem?
Practice N-th Tribonacci Number with our built-in code editor and test cases.
Practice on FleetCode