N-th Tribonacci Number solution and explanation
Google
9 more videos on this problem
N-th Tribonacci Number - Leetcode 1137NeetCodeIO · 4:14 · 14K views
N-th Tribonacci Number - LeetCode 1137 - Python #leetcode75 #dynamicprogrammingDeepti Talesra · 7:26 · 1K views
N-th Tribonacci Number | Leetcode - 1137 | Python | Coding InterviewTechError · 12:36 · 411 views
1137. N-th Tribonacci Number | JavaScript | O(n) TC | O(1) SC | LeetCode Daily ChallengeLeetCodeWithMonu · 4:19 · 324 views
Leetcode 1137 | N-th Tribonacci Number using dynamic programming | Fastest solutionJoey'sTech · 6:06 · 264 views
1137. N-th Tribonacci Number | LeetCodeDeep Tech · 5:00 · 257 views
N-th Tribonacci Number | LeetCode 1137 | Coders CampCoders Camp · 4:42 · 219 views
#3 Dynamic Programming Introduction | Solving LeetCode 1137 N-th Tribonacci Number | Get started!Code Harmony · 20:04 · 218 views
Python Solution to Leetcode 1137: N-th Tribonacci NumberMohit Bodhija · 3:54 · 199 views
Daily Leetcode #1035: Jan 30, 2023 - 1137. N-th Tribonacci NumberProgramming Live with Larry · 4:29 · 187 views
The problem
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.
def tribonacci(n):
if n == 0: return 0
if n == 1 or n == 2: return 1
t0, t1, t2 = 0, 1, 1
for _ in range(3, n + 1):
t = t0 + t1 + t2
t0, t1, t2 = t1, t2, t
return t
n = 25
print(tribonacci(n))public class Tribonacci {
public static int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
int t0 = 0, t1 = 1, t2 = 1;
int t = 0;
for (int i = 3; i <= n; i++) {
t = t0 + t1 + t2;
t0 = t1;
t1 = t2;
t2 = t;
}
return t;
}
public static void main(String[] args) {
int n = 25;
System.out.println(tribonacci(n));
}
}#include <iostream>
int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
int t0 = 0, t1 = 1, t2 = 1;
int t = 0;
for (int i = 3; i <= n; ++i) {
t = t0 + t1 + t2;
t0 = t1;
t1 = t2;
t2 = t;
}
return t;
}
int main() {
int n = 25;
std::cout << tribonacci(n);
return 0;
}function tribonacci(n) {
if (n === 0) return 0;
if (n === 1 || n === 2) return 1;
let t0 = 0, t1 = 1, t2 = 1;
let t = 0;
for (let i = 3; i <= n; i++) {
t = t0 + t1 + t2;
t0 = t1;
t1 = t2;
t2 = t;
}
return t;
}
let n = 25;
console.log(tribonacci(n));#include <stdio.h>
int tribonacci(int n){
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
int t0 = 0, t1 = 1, t2 = 1;
int t = 0;
for (int i = 3; i <= n; i++) {
t = t0 + t1 + t2;
t0 = t1;
t1 = t2;
t2 = t;
}
return t;
}
int main() {
int n = 25;
printf("%d", tribonacci(n));
return 0;
}using System;
public class Program
{
public static int Tribonacci(int n)
{
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
int t0 = 0, t1 = 1, t2 = 1;
int t = 0;
for (int i = 3; i <= n; i++)
{
t = t0 + t1 + t2;
t0 = t1;
t1 = t2;
t2 = t;
}
return t;
}
public static void Main()
{
int n = 25;
Console.WriteLine(Tribonacci(n));
}
}The Python solution employs a tuple to succinctly swap and iterate through the sequence values.
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.
def tribonacci(n, memo={0: 0, 1: 1, 2: 1}):
if n in memo:
return memo[n]
memo[n] = tribonacci(n-1, memo) + tribonacci(n-2, memo) + tribonacci(n-3, memo)
return memo[n]
n = 25
print(tribonacci(n))#include <iostream>
#include <unordered_map>
int tribonacci(int n, std::unordered_map<int, int>& memo) {
if (memo.find(n) != memo.end()) {
return memo[n];
}
memo[n] = tribonacci(n-1, memo) + tribonacci(n-2, memo) + tribonacci(n-3, memo);
return memo[n];
}
int main() {
std::unordered_map<int, int> memo = {{0, 0}, {1, 1}, {2, 1}};
int n = 25;
std::cout << tribonacci(n, memo) << std::endl;
return 0;
}In this Python code, a dictionary is used as a memoization cache, storing the results of each calculated Tribonacci number.
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.
function tribonacci(n: number): number {
let [a, b, c] = [0, 1, 1];
while (n--) {
let d = a + b + c;
a = b;
b = c;
c = d;
}
return a;
}func tribonacci(n int) int {
a, b, c := 0, 1, 1
for i := 0; i < n; i++ {
a, b, c = b, c, a+b+c
}
return a
}class Solution {
/**
* @param Integer $n
* @return Integer
*/
function tribonacci($n) {
$a = 0;
$b = 1;
$c = 1;
while ($n--) {
$d = $a + $b + $c;
$a = $b;
$b = $c;
$c = $d;
}
return $a;
}
}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)$.
function tribonacci(n: number): number {
if (n === 0) {
return 0;
}
if (n < 3) {
return 1;
}
const a = [
[1, 1, 0],
[1, 0, 1],
[1, 0, 0],
];
return pow(a, n - 3)[0].reduce((a, b) => a + b);
}
function mul(a: number[][], b: number[][]): number[][] {
const [m, n] = [a.length, b[0].length];
const c = Array.from({ length: m }, () => Array.from({ length: n }, () => 0));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
for (let k = 0; k < b.length; ++k) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
return c;
}
function pow(a: number[][], n: number): number[][] {
let res = [[1, 1, 0]];
while (n) {
if (n & 1) {
res = mul(res, a);
}
a = mul(a, a);
n >>= 1;
}
return res;
}func tribonacci(n int) (ans int) {
if n == 0 {
return 0
}
if n < 3 {
return 1
}
a := [][]int{{1, 1, 0}, {1, 0, 1}, {1, 0, 0}}
res := pow(a, n-3)
for _, x := range res[0] {
ans += x
}
return
}
func mul(a, b [][]int) [][]int {
m, n := len(a), len(b[0])
c := make([][]int, m)
for i := range c {
c[i] = make([]int, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
for k := 0; k < len(b); k++ {
c[i][j] += a[i][k] * b[k][j]
}
}
}
return c
}
func pow(a [][]int, n int) [][]int {
res := [][]int{{1, 1, 0}}
for n > 0 {
if n&1 == 1 {
res = mul(res, a)
}
a = mul(a, a)
n >>= 1
}
return res
}class Solution {
/**
* @param Integer $n
* @return Integer
*/
function tribonacci($n) {
if ($n === 0) {
return 0;
}
if ($n < 3) {
return 1;
}
$a = [[1, 1, 0], [1, 0, 1], [1, 0, 0]];
$res = $this->pow($a, $n - 3);
return array_sum($res[0]);
}
private function mul($a, $b) {
$m = count($a);
$n = count($b[0]);
$p = count($b);
$c = array_fill(0, $m, array_fill(0, $n, 0));
for ($i = 0; $i < $m; ++$i) {
for ($j = 0; $j < $n; ++$j) {
for ($k = 0; $k < $p; ++$k) {
$c[$i][$j] += $a[$i][$k] * $b[$k][$j];
}
}
}
return $c;
}
private function pow($a, $n) {
$res = [[1, 1, 0]];
while ($n > 0) {
if ($n & 1) {
$res = $this->mul($res, $a);
}
$a = $this->mul($a, $a);
$n >>= 1;
}
return $res;
}
}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 | – |
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 |
Frequently asked questions
Is N-th Tribonacci Number easy or hard?
N-th Tribonacci Number is categorized as an Easy problem on LeetCode with an acceptance rate above 60%. The main challenge is recognizing the recurrence and translating it into a dynamic programming loop without unnecessary memory usage.
N-th Tribonacci Number Python/Java solution
Python, Java, C++, and JavaScript implementations typically use a loop that updates three variables representing T(n-3), T(n-2), and T(n-1). Each iteration computes the next value and shifts the variables forward. The logic is identical across languages and runs in O(n) time with O(1) space.
How to solve N-th Tribonacci Number in O(n)?
Initialize the base values T0 = 0, T1 = 1, and T2 = 1. Iterate from index 3 up to n, computing the next value as the sum of the previous three numbers. Update the tracking variables after each step. This bottom-up dynamic programming approach evaluates the recurrence in O(n) time with constant space.
What is the best approach for N-th Tribonacci Number?
The best approach is iterative dynamic programming using three variables to track the last three Tribonacci values. It runs in O(n) time and O(1) space because each step only requires the previous three numbers. This avoids recursion overhead and extra memory while still following the recurrence relation.
Is N-th Tribonacci Number asked at Google/Amazon/Meta?
Tribonacci-style recurrence problems appear in interviews at companies like Amazon and Google as variations of Fibonacci and dynamic programming questions. They test whether candidates recognize overlapping subproblems and convert recursive definitions into efficient DP solutions.
What data structure is used in N-th Tribonacci Number?
Most solutions use simple variables or a small array to store previous values in the sequence. Memoized recursion may use an array or hash map as a cache. The optimized solution only requires three integer variables to maintain the last three computed values.
What is the time complexity of N-th Tribonacci Number?
The optimal time complexity is O(n) because the algorithm iterates once from 3 to n and computes each Tribonacci value exactly once. Recursive solutions without memoization would take exponential time, but memoization or bottom-up dynamic programming reduces it to linear time.