Problem overview
The method tribonacci(n) returns T(n). The Tribonacci sequence starts with T(0) = 0, T(1) = 1, T(2) = 1, and each later number is the sum of the three before it: T(n) = T(n - 1) + T(n - 2) + T(n - 3). The values run 0, 1, 1, 2, 4, 7, 13, 24.
In the examples, T(3) = 1 + 1 + 0 = 2, T(4) = 2 + 1 + 1 = 4 and T(5) = 4 + 2 + 1 = 7. The statement asks for O(n) time and O(1) space.
Approach: slide a window of three
This is the Fibonacci idea with one more value. Each number depends only on the three before it, so you never need the whole sequence: three variables are enough. Name them by how old they are. curr is the newest value, prev is one step behind and prev2 is two steps behind. Start them at T(2), T(1) and T(0), then repeat: compute the next number as the sum of the three, and shift each variable one place back.
A direct recursive version would call itself three times for every value and repeat the same computations many times, so its running time grows exponentially. The loop computes each number once.
Counting the calls of a plain recursive version makes the difference concrete: it makes 289 calls for n = 10, 128,287 for n = 20 and 56,843,233 for n = 30. The loop does 8, 18 and 28 additions for the same inputs.
One detail makes the early return work. For n = 0 and n = 1 the answer is the input itself, but n = 2 gives 1 as well, and 2 is not equal to 1. That is why the check is n < 2 and not n < 3: the value for n = 2 comes from the starting value of curr, not from the early return.
Fibonacci with a bigger window
The only differences from the two-variable Fibonacci loop are the number of variables and the starting point. With two values the loop starts at 2 and the window is F(i - 2) and F(i - 1). With three values the loop starts at 3, because the three starting numbers T(0), T(1) and T(2) are already in the window. The same idea works for any fixed window size: hold the last k values, add them, and shift. It stays O(1) in space for any constant k. A version that stored the whole sequence in an array would also be O(n) in time but would need O(n) space, which the statement rules out.
Step by step
- Handle
n < 2.T(0) = 0andT(1) = 1equaln, so returnnfor them. - Declare the three variables in a single
let, separated by commas:prev2 = 0,prev = 1,curr = 1. They holdT(0),T(1)andT(2). Forn = 2the loop below doesn't run andcurr, which isT(2), is returned directly. - Loop from 3 to
n, withi <= nso thatnitself is computed. - Compute
nextasprev2 + prev + curr. - Shift the values, oldest first. Assign
prevtoprev2, thencurrtoprev, thennexttocurr. Each variable is overwritten only after its old value has been copied one place back. - Return
currafter the loop.
Trace n = 5. The state starts as (prev2, prev, curr) = (0, 1, 1). At i = 3, next = 2, and the state becomes (1, 1, 2). At i = 4, next = 4 and the state becomes (1, 2, 4). At i = 5, next = 7 and the state becomes (2, 4, 7). The method returns 7.
The solution in TypeScript
class Solution {
tribonacci(n: number): number {
if (n < 2) {
return n;
}
let prev2 = 0, prev = 1, curr = 1;
for (let i = 3; i <= n; i++) {
let next = prev2 + prev + curr;
prev2 = prev;
prev = curr;
curr = next;
}
return curr;
}
}The three variables are declared together and inferred as number. The three shifting assignments are separate statements run in order, and they can't be reordered: if you wrote prev = curr before prev2 = prev, the old prev would be lost. JavaScript also lets you swap with destructuring, [prev2, prev, curr] = [prev, curr, next], which does all three at once, but the plain assignments make the order visible.
All numbers in TypeScript are doubles. The results are exact only while they stay below 2^53. The Tribonacci numbers grow faster than the Fibonacci numbers, and tribonacci(63) is already beyond the safe-integer range, so the result can no longer be trusted from there. The lesson's inputs are small enough not to reach it.
Complexity
The loop runs n - 2 times and does a constant amount of work each time, so the time is O(n). The method stores four numbers, prev2, prev, curr and next, plus the index, so the extra space is O(1).
Edge cases and common mistakes
- Small
n.n = 0andn = 1returnnthrough the early check.n = 2skips the loop and returns the startingcurr, which is 1. - Starting at the wrong values. The sequence starts 0, 1, 1, unlike a version that starts 0, 0, 1. Make sure
currbegins as 1. - Starting the loop at 2. That would compute
T(2)again and produce a value one step too far. - Shifting in the wrong order. Updating
currfirst leaves nothing to copy intoprev. - Stopping at
i < n. The method would returnT(n - 1). - Negative or fractional
n. The lesson promises a non-negative integer. A negativenwould pass the early check and be returned unchanged, which is not a sequence value, and thenumbertype does not stop a caller from passing it. Validate the input if the method is used outside the lesson.
Testing
Try n = 3 (2), n = 4 (4), n = 10 (149) and n = 2 (1).