Difficulty: 🟢 Easy
Topics: Math, Dynamic Programming, Memoization

Solution

LeetCode 1137, N-th Tribonacci Number

Problem Understanding

The problem asks us to compute the n-th number in the Tribonacci sequence.

The Tribonacci sequence is very similar to the Fibonacci sequence, except that instead of summing the previous two numbers, each value is formed by summing the previous three numbers.

The sequence is defined as:

T0 = 0
T1 = 1
T2 = 1

For every value after that:

$T_{n+3}=T_n+T_{n+1}+T_{n+2}$

The input consists of a single integer n, representing the index of the Tribonacci number we need to return. The output is the value of Tn.

For example:

n = 4
The sequence becomes: 0, 1, 1, 2, 4
Therefore, T4 = 4

The constraints are very small:

0 <= n <= 37
The result always fits in a 32-bit signed integer

These constraints tell us several important things:

Exponential recursion might technically pass because n is small.
However, the problem is designed to teach dynamic programming or memoization.
An efficient linear solution is straightforward and preferred.
Integer overflow is not a concern in Python, and is also safe in Go because the answer fits within 32-bit integer range.

There are several important edge cases:

n = 0, we must return 0
n = 1, we must return 1
n = 2, we must return 1

These base cases are critical because the recurrence relation only works for values greater than or equal to 3. A naive implementation that immediately starts recurrence computation without handling these cases can produce incorrect results or index errors.

Approaches

Brute Force Recursive Approach

The most direct approach is to implement the recurrence relation exactly as written.

For each n, we recursively compute:

tribonacci(n - 1)
tribonacci(n - 2)
tribonacci(n - 3)

and sum them together.

This approach is mathematically correct because it follows the problem definition directly. However, it is extremely inefficient because the same subproblems are recomputed many times.

For example, computing tribonacci(25) repeatedly recalculates values like tribonacci(20) and tribonacci(18) over and over again.

The recursion tree grows exponentially, making this solution unnecessarily slow.

Optimal Dynamic Programming Approach

The key observation is that each Tribonacci number depends only on the previous three values.

That means we do not need recursion at all. We can iteratively build the sequence from the bottom up.

At any step, we only need to remember:

the previous third value
the previous second value
the previous first value

Using these three variables, we can compute the next Tribonacci number in constant time.

This transforms the solution into a simple linear iteration with constant extra memory.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(3^n)	O(n)	Recursive recomputation causes exponential growth
Optimal	O(n)	O(1)	Iterative dynamic programming using three variables

Algorithm Walkthrough

Optimal Iterative Dynamic Programming Algorithm

First, handle the base cases directly.

If n is:

0, return 0
1 or 2, return 1

These values are explicitly defined by the problem. 2. Initialize three variables to represent the most recent Tribonacci numbers.

We start with:

first = 0
second = 1
third = 1

These correspond to:

T0
T1
T2

Iterate from 3 up to n.

For each position:

Compute the next Tribonacci value as:

next_value = first + second + third 4. Shift the window forward.

After computing the new value:

first becomes second
second becomes third
third becomes next_value

This maintains the invariant that the variables always represent the three most recent Tribonacci numbers. 5. After the loop finishes, return third.

At that point, third stores Tn.

Why it works

The algorithm maintains a sliding window containing the last three Tribonacci values at every iteration.

Initially:

first = T0
second = T1
third = T2

During each iteration, we compute:

next_value = T(n-3) + T(n-2) + T(n-1)

which exactly matches the Tribonacci recurrence definition.

After shifting the variables forward, the invariant remains true for the next iteration. Because the recurrence relation is applied correctly at every step, the final value stored in third is guaranteed to be the correct Tn.

Python Solution

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        
        if n == 1 or n == 2:
            return 1
        
        first, second, third = 0, 1, 1
        
        for _ in range(3, n + 1):
            next_value = first + second + third
            first = second
            second = third
            third = next_value
        
        return third

The implementation begins by handling the three base cases directly. This avoids unnecessary iteration and ensures correctness for the smallest inputs.

The variables first, second, and third store the three most recent Tribonacci numbers. Initially, they represent T0, T1, and T2.

The loop runs from 3 through n, inclusive. During each iteration, the next Tribonacci number is computed by summing the previous three values.

After computing next_value, the variables are shifted forward so that they continue representing the most recent three sequence values.

At the end of the loop, third contains the answer.

Go Solution

func tribonacci(n int) int {
    if n == 0 {
        return 0
    }

    if n == 1 || n == 2 {
        return 1
    }

    first, second, third := 0, 1, 1

    for i := 3; i <= n; i++ {
        nextValue := first + second + third
        first = second
        second = third
        third = nextValue
    }

    return third
}

The Go implementation follows exactly the same logic as the Python solution.

One small difference is that Go requires explicit variable declarations using :=.

There are no concerns about integer overflow because the problem guarantees the result fits within a 32-bit signed integer range. Go's int type safely handles these values.

Unlike Python, Go does not support tuple assignment in exactly the same flexible way, so the variables are updated individually.

Worked Examples

Example 1

Input:

n = 4

Initial state:

Variable	Value
first	0
second	1
third	1

The loop runs from 3 to 4.

Iteration for i = 3

next_value = 0 + 1 + 1 = 2

Update variables:

Variable	New Value
first	1
second	1
third	2

Iteration for i = 4

next_value = 1 + 1 + 2 = 4

Update variables:

Variable	New Value
first	1
second	2
third	4

Loop ends.

Return:

Example 2

Input:

n = 25

The sequence evolves iteratively until index 25.

A shortened trace:

Index	Tribonacci Value
0	0
1	1
2	1
3	2
4	4
5	7
6	13
7	24
8	44
...	...
25	1389537

Final result:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We compute each Tribonacci number exactly once
Space	O(1)	Only three variables are stored regardless of input size

The algorithm performs a single loop from 3 to n, making the runtime linear in relation to the input size.

The memory usage remains constant because we never store the entire sequence. Only the previous three values are needed at any time.

Test Cases

solution = Solution()

assert solution.tribonacci(0) == 0  # smallest possible input
assert solution.tribonacci(1) == 1  # first base case
assert solution.tribonacci(2) == 1  # second base case
assert solution.tribonacci(3) == 2  # first computed Tribonacci value
assert solution.tribonacci(4) == 4  # provided example
assert solution.tribonacci(5) == 7  # verifies recurrence continues correctly
assert solution.tribonacci(6) == 13  # additional recurrence validation
assert solution.tribonacci(10) == 149  # medium-sized input
assert solution.tribonacci(25) == 1389537  # provided example
assert solution.tribonacci(37) == 2082876103  # maximum constraint

Test	Why
`n = 0`	Verifies smallest boundary value
`n = 1`	Verifies first base case
`n = 2`	Verifies second base case
`n = 3`	Verifies first recurrence computation
`n = 4`	Matches provided example
`n = 5`	Ensures iterative updates remain correct
`n = 6`	Further validates recurrence progression
`n = 10`	Tests medium-sized iteration
`n = 25`	Matches provided example
`n = 37`	Verifies upper constraint handling

Edge Cases

Edge Case 1, `n = 0`

This is the smallest valid input. It can easily cause bugs if the implementation assumes the sequence always begins with positive values.

The implementation explicitly checks for n == 0 and immediately returns 0, avoiding any unnecessary computation or incorrect indexing logic.

Edge Case 2, `n = 1` or `n = 2`

These values are special because they are predefined base cases and are not generated by the recurrence relation.

A solution that blindly enters the loop without handling these cases may incorrectly compute values or access invalid previous states.

The implementation handles both cases directly by returning 1.

Edge Case 3, Maximum Input `n = 37`

Although the input range is small, the values grow quickly.

A recursive brute-force solution would still perform a large number of repeated computations. While it may technically pass for this constraint, it is inefficient and scales poorly.

The iterative dynamic programming solution handles the maximum input efficiently in linear time while using constant memory.

LeetCode 1137 - N-th Tribonacci Number