N-th Tribonacci Number
Compute the n-th Tribonacci number, the sum of the three before it, bottom-up with three rolling variables instead of recursion or a full table.
Problem Understanding
N-th Tribonacci Number (LeetCode 1137): the Tribonacci sequence is T(0) = 0, T(1) = 1, T(2) = 1, and T(n + 3) = T(n) + T(n + 1) + T(n + 2). Given n (0 ≤ n ≤ 37), return T(n).
Examples: n = 4 → 4 (0, 1, 1, 2, 4); n = 25 → 1389537.
The Intuition: Fibonacci With One More Term
Each value depends only on the three before it, so build the sequence from the bottom and keep a window of three.
- Handle n < 3 directly.
- Hold three values, a, b and c, starting at T(0), T(1), T(2).
- Slide the window: the next value is a + b + c, and the window moves up by one.
It is Fibonacci Number with one more term, and the same rolling-variable idea that keeps Min Cost Climbing Stairs at O(1) space.
Interactive Walkthrough
a, b, c = 0, 1, 1
T(i), index below
a
0
b
1
c
2
a + b
1
c
1
Answer
:
Start with a = T(0) = 0, b = T(1) = 1 and c = T(2) = 1
Next
T(3) = 0 + 1 + 1 = 2. Slide: a = 1, b = 1, c = 2
n
One cell per T(i). The three tinted cells are a, b and c, the only values the code still holds; everything to their left has been forgotten. Try n = 25 to see how few steps the loop needs.
Dry Run Table
Input: n = 6.
| i | a | b | c = T(i) |
|---|---|---|---|
| start | 0 | 1 | 1 |
| 3 | 1 | 1 | 2 |
| 4 | 1 | 2 | 4 |
| 5 | 2 | 4 | 7 |
| 6 | 4 | 7 | 13 |
Answer: 13.
The Solution Template
Base cases, then a loop that slides three variables. Java, C++ and C use a temporary for the new value, since they cannot assign all three at once.
N-th Tribonacci Number Code
1var tribonacci = function(n) {2 if (n < 3) {3 return n === 0 ? 0 : 1;4 }5 let a = 0, b = 1, c = 1;6 for (let i = 3; i <= n; i++) {7 [a, b, c] = [b, c, a + b + c];8 }9 return c;10};
Edge Cases & Common Mistakes
- n = 0: the answer is 0, not 1.
- n = 1 or 2: both are 1; the loop must not run.
- Updating in the wrong order: setting a = b before computing a + b + c loses the old a. Compute the next value first, or assign all three at once.
- Recursion without memoisation: about 3^n calls; it times out well before n = 37.
Summary
Return the base cases directly, then slide three variables from T(0), T(1), T(2) up to T(n), each new value the sum of the three. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet