N-th Tribonacci Number

Difficulty: Easy Source: NeetCode

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

Example 2: Input: n = 25 Output: 1389537

Constraints:

• 0 <= n <= 37
• The answer is guaranteed to fit in a 32-bit integer.

Prerequisites

Before attempting this problem, you should be comfortable with:

• Fibonacci Sequence — understanding recurrence relations
• Dynamic Programming — bottom-up DP with rolling variables
• Memoization — caching recursive results

1. Brute Force (Recursion)

Intuition

Directly implement the recurrence: T(n) = T(n-1) + T(n-2) + T(n-3). Without caching, this is an exponential tree of recursive calls — the same values get recomputed many times. For n=37 this is manageable in practice but bad in theory.

Algorithm

1. Base cases: T(0) = 0, T(1) = 1, T(2) = 1.
2. Recursive case: T(n) = T(n-1) + T(n-2) + T(n-3).

Solution

def tribonacci_brute(n):
    if n == 0:
        return 0
    if n <= 2:
        return 1
    return tribonacci_brute(n - 1) + tribonacci_brute(n - 2) + tribonacci_brute(n - 3)


print(tribonacci_brute(0))   # 0
print(tribonacci_brute(1))   # 1
print(tribonacci_brute(4))   # 4
print(tribonacci_brute(10))  # 149

Complexity

• Time: O(3^n) — three branches at each level
• Space: O(n) — recursion stack

2. Dynamic Programming (Rolling Variables)

Intuition

Since each Tribonacci number only depends on the previous three, there’s no need to store the entire sequence. Use three rolling variables — a, b, c — representing T(n-3), T(n-2), T(n-1). Each iteration computes T(n) = a + b + c and slides the window forward.

Algorithm

1. Initialize a = 0 (T0), b = 1 (T1), c = 1 (T2).
2. Handle the base cases directly.
3. For each step from 3 to n: compute d = a + b + c, then a, b, c = b, c, d.
4. Return c.

Solution

def tribonacci(n):
    if n == 0:
        return 0
    if n <= 2:
        return 1

    a, b, c = 0, 1, 1  # T0, T1, T2

    for _ in range(3, n + 1):
        a, b, c = b, c, a + b + c

    return c


print(tribonacci(0))   # 0
print(tribonacci(1))   # 1
print(tribonacci(2))   # 1
print(tribonacci(3))   # 2
print(tribonacci(4))   # 4
print(tribonacci(25))  # 1389537
print(tribonacci(37))  # 2082876103

Complexity

• Time: O(n) — one pass from 3 to n
• Space: O(1) — only three variables

Common Pitfalls

Getting base cases wrong. T0 = 0, T1 = 1, T2 = 1 — notice that T1 and T2 are both 1, not 0 and 1. Mixing these up shifts the entire sequence.

Off-by-one in the loop range. The loop should start at 3 and go up to and including n. If your loop starts at 2, you overwrite T2 incorrectly.

Returning the wrong variable. After the loop, c holds T(n). If you accidentally return b, you get T(n-1).