N-th Tribonacci Number — InterviewPrepKit

Solving tips

This is Fibonacci with a 3-wide look-back: T(k) = T(k-1)+T(k-2)+T(k-3).
Slide three rolling variables with simultaneous assignment a,b,c = b,c,a+b+c for O(n) time, O(1) space.
Get the base cases right: T(0)=0, T(1)=1, T(2)=1 (note T(2) is 1, not 2), and short-circuit n<3.
Avoid plain recursion - three branches per call is ~O(3^n) and re-derives lower terms billions of times.

Problem

The Tribonacci sequence is defined by:

T(0) = 0, T(1) = 1, T(2) = 1
T(k) = T(k-1) + T(k-2) + T(k-3) for k >= 3

Given an integer n, return T(n).

Examples

n = 4 → 4 — the sequence starts 0, 1, 1, 2, 4; T(3) = 0+1+1 = 2, T(4) = 1+1+2 = 4.
n = 25 → 1389537.
n = 0 → 0 — the very first term.

Constraints

0 <= n <= 37
The answer fits in a signed 32-bit integer.

Like Fibonacci, the tiny bound means any linear method is trivial; the trap is the exponential naive recursion, which re-expands three branches per call.

Think about it first

Hint 1

This is Fibonacci with a window of *three* previous terms instead of two. Write the recurrence directly, then worry about not recomputing.

Hint 2

Plain recursion makes three recursive calls each level → roughly `3^n` work, all of it recomputing the same terms. Cache each `T(k)`, or better, build up from `T(0)` in a loop.

Hint 3

Bottom-up you only ever need the last three values. Keep three variables `a, b, c` and slide them forward: `a, b, c = b, c, a+b+c`. O(n) time, O(1) space. Handle `n < 3` as base cases.

TL;DR

Slide a 3-wide window of previous terms forward — O(n) time, O(1) space.

The recurrence

T(k) = T(k-1) + T(k-2) + T(k-3)   for k >= 3
T(0) = 0,  T(1) = 1,  T(2) = 1

Approach 1 — Brute-force recursion

Transcribe the recurrence; each call fans out into three.

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n <= 2:
            return 1
        return (self.tribonacci(n - 1)
                + self.tribonacci(n - 2)
                + self.tribonacci(n - 3))

Complexity: ~O(3^n) time, O(n) stack.

Why the constraints kill it: at n = 37 the three-way branching re-derives lower terms billions of times — far slower than the linear methods below despite the small n.

Approach 2 — Top-down memoization

The insight: there are only n + 1 distinct terms; cache each so it is computed once.

from functools import cache

class Solution:
    def tribonacci(self, n: int) -> int:
        @cache
        def T(k: int) -> int:
            if k == 0:
                return 0
            if k <= 2:
                return 1
            return T(k - 1) + T(k - 2) + T(k - 3)
        return T(n)

Complexity: O(n) time, O(n) space (cache + stack).

Approach 3 — Bottom-up tabulation

The insight: compute T(0), T(1), … , T(n) in order so each term’s three predecessors are already stored.

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n <= 2:
            return 1
        dp = [0] * (n + 1)
        dp[1] = dp[2] = 1
        for k in range(3, n + 1):
            dp[k] = dp[k - 1] + dp[k - 2] + dp[k - 3]
        return dp[n]

Walkthrough (n = 4): dp = [0, 1, 1, ?, ?]. dp[3] = 1+1+0 = 2, dp[4] = 2+1+1 = 4. Return 4. ✓

Complexity: O(n) time, O(n) space.

Approach 4 — Space-optimized (rolling triple)

The insight: T(k) reads only the previous three terms, so three variables replace the whole table.

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n <= 2:
            return 1
        a, b, c = 0, 1, 1                 # T(0), T(1), T(2)
        for _ in range(3, n + 1):
            a, b, c = b, c, a + b + c
        return c

Walkthrough (n = 25): starting (a,b,c) = (0,1,1), each step drops the oldest term and appends the new sum. After 23 iterations c = 1389537. ✓

Complexity: O(n) time, O(1) space.

Common pitfalls

Wrong base cases. Note T(2) = 1, not 2. A wrong seed (e.g. treating it like Fibonacci with only two bases) shifts the whole sequence.
Not short-circuiting n < 3. The rolling-triple loop assumes at least the three seeds exist; return the base values directly for n = 0, 1, 2.
Sliding the window in the wrong order. Use simultaneous assignment a, b, c = b, c, a+b+c; updating a before computing the sum corrupts it.

Pattern takeaway

Tribonacci generalizes the Fibonacci DP from a 2-wide to a 3-wide look-back window — the same “split on the last decision” logic, just with one more term in the sum. The reusable rule: when a recurrence depends on a fixed constant number w of previous states, tabulate bottom-up and then keep only the last w values as rolling variables for O(1) space.