Log inSign up
easyLeetCodeNot Started

N-th Tribonacci Number

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

The Tribonacci sequence T_n is defined as follows:

T_0 = 0, T_1 = 1, T_2 = 1, and T_{n+3} = T_n + T_{n+1} + T_{n+2} for n >= 0.

Given n, return the value of T_n.

### 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 <= 231 - 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Generalize 2-term linear recurrences (Fibonacci) to 3-term recurrences.
  • Maintain constant rolling state variables.
  • Recognize logarithmic matrix exponentiation potential.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sequence defined by 3 base values.
  • Recurrence relation summing the last 3 elements.

Algorithmic Decision Tree:

  • Return base cases immediately if n <= 2.
  • Iterate from 3 to n with 3 rolling variables.

Connected Patterns:

Fibonacci NumberClimbing Stairs

1. Direct Recursion

Intuition

Recursively evaluate T(n) = T(n-1) + T(n-2) + T(n-3).

Algorithm

  1. If n == 0, return 0.
  2. If n == 1 || n == 2, return 1.
  3. Return solve(n - 1) + solve(n - 2) + solve(n - 3).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 int tribonacci(int n) {
8 if (n == 0) return 0;
9 if (n == 1 || n == 2) return 1;
10 return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
11 }
12};
13
14int main() {
15 Solution sol;
16 cout << "Tribonacci(4): " << sol.tribonacci(4) << endl;
17 return 0;
18}

Time & Space Complexity

  • Time complexity: O(3^n)
  • Space complexity: O(n) call stack

2. 1D Array DP

Intuition

Pre-allocate array dp of size n + 3, iteratively fill indices 3 to n.

Algorithm

  1. If n == 0, return 0.
  2. If n <= 2, return 1.
  3. Allocate dp[n + 1] with dp[0] = 0, dp[1] = 1, dp[2] = 1.
  4. Loop i from 3 to n: dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3].
  5. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int tribonacci(int n) {
9 if (n == 0) return 0;
10 if (n <= 2) return 1;
11
12 vector<int> dp(n + 1);
13 dp[0] = 0; dp[1] = 1; dp[2] = 1;
14
15 for (int i = 3; i <= n; ++i) {
16 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
17 }
18
19 return dp[n];
20 }
21};
22
23int main() {
24 Solution sol;
25 cout << "Tribonacci(4): " << sol.tribonacci(4) << endl;
26 return 0;
27}

Time & Space Complexity

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

3. Space-Optimized 3-Variable DP (O(1) Space)

Intuition

Maintain three variables: t0, t1, t2. Update sequentially in a loop.

Algorithm

  1. If n == 0, return 0.
  2. If n <= 2, return 1.
  3. Initialize t0 = 0, t1 = 1, t2 = 1.
  4. Loop from 3 to n:
  5. t3 = t0 + t1 + t2.
  6. t0 = t1.
  7. t1 = t2.
  8. t2 = t3.
  9. Return t2.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 int tribonacci(int n) {
8 if (n == 0) return 0;
9 if (n <= 2) return 1;
10
11 int t0 = 0, t1 = 1, t2 = 1;
12 for (int i = 3; i <= n; ++i) {
13 int t3 = t0 + t1 + t2;
14 t0 = t1;
15 t1 = t2;
16 t2 = t3;
17 }
18
19 return t2;
20 }
21};
22
23int main() {
24 Solution sol;
25 cout << "Tribonacci(4): " << sol.tribonacci(4) << endl;
26 return 0;
27}

Time & Space Complexity

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

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Direct RecursionO(3^n)O(n)Recursive evaluation of recurrence tree.Subproblem overlap
2.1D Array DPO(n)O(n)Tabulate values up to index n.Array allocation
3.3-Variable Rolling DPOptimalO(n)O(1)Store only the last 3 values.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Returning 1 for n = 0 (confusing it with Fibonacci where F(0) = 0, but Tribonacci base is T(0) = 0, T(1) = 1, T(2) = 1).

Pitfall 2:

Overwriting rolling variables before their values are used in subsequent assignments.

Crucial Edge Cases to Validate:

  • n = 0: Must return 0.
  • n = 1: Must return 1.
  • n = 2: Must return 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that for extremely large n (e.g., n = 109), the recurrence can be computed in O(log n) using 3x3 matrix exponentiation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How many prior state values must be kept in memory to compute the next Tribonacci number?

Back to DSA Sheet