Tribonacci Number LeetCode 1137 Guide

LeetCode 1137 N-th Tribonacci Number asks you to compute T(n) given the recurrence T(0)=0, T(1)=1, T(2)=1, and T(n)=T(n-1)+T(n-2)+T(n-3) for all n>=3. The problem guarantees 0<=n<=37, so the largest answer fits in a 32-bit integer without overflow. Your task is simply to return the n-th value in this sequence.

Unlike Fibonacci, which sums the previous two terms, Tribonacci sums the previous three. The base cases anchor the recurrence at T(0), T(1), and T(2), then every subsequent term is determined. The sequence begins 0, 1, 1, 2, 4, 7, 13, 24, 44, 81 and grows roughly 1.839 times per step.

The problem is rated Easy on LeetCode because once you recognize it as a Fibonacci variant the implementation is mechanical. The core skill is extending a two-variable rolling technique to three variables, which is a natural stepping stone to more complex DP problems involving sliding windows of prior results.

The classic Fibonacci rolling-variable solution uses two variables: prev and curr. At each step you compute next=prev+curr, then shift prev=curr and curr=next. After n steps, curr holds F(n). This approach requires O(n) time and O(1) space — no array, no recursion stack.

Tribonacci extends this by one variable. Instead of two rolling variables you maintain three: a, b, and c representing T(n-3), T(n-2), and T(n-1) respectively. At each step compute next=a+b+c, then shift a=b, b=c, c=next. The pattern is structurally identical to Fibonacci — just one extra variable and one extra addend in the sum.

This insight means that if you already understand the Fibonacci rolling-variable approach, Tribonacci is a direct mechanical extension. The variable naming changes slightly and the sum has three terms instead of two, but every other aspect of the algorithm — loop bounds, base cases, return value — follows the same blueprint.

The rolling-variables algorithm runs in O(n) time and O(1) space. Initialize a=0, b=1, c=1 matching the base cases T(0), T(1), T(2). Then loop from i=3 up to and including n. In each iteration compute next=a+b+c, then shift: a=b, b=c, c=next. After the loop, c holds T(n).

Before entering the loop, handle the three base cases explicitly: if n==0 return 0; if n==1 or n==2 return 1. This guards against running the loop zero or negative times and ensures the return value c is always valid when n>=3.

The shift step is critical. In Python you can do this atomically with tuple assignment: a, b, c = b, c, a+b+c — this evaluates the right-hand side first, avoiding the need for a temporary variable. In Java you must store next=a+b+c in a temp variable before reassigning a and b, otherwise the overwritten values corrupt the sum.

The top-down memoization approach uses a recursive function with a cache. Define trib(n): if n==0 return 0; if n<=2 return 1; if n in memo return memo[n]; memo[n] = trib(n-1)+trib(n-2)+trib(n-3); return memo[n]. In Python this is one line with @functools.lru_cache(None) decorating the function.

Memoization is conceptually simple — it mirrors the recurrence definition directly — and avoids having to think about the iterative shift order. The trade-off is O(n) space for the cache and O(n) stack depth for the recursion, compared to O(1) space for the rolling-variable approach.

For n<=37 the space difference is negligible in practice, but in interviews the rolling-variable approach is the expected answer because it demonstrates deliberate space optimization. Memoization is a valid fallback if you blank on the iterative approach, but knowing both solutions shows deeper mastery.

Starting from the base cases: T(0)=0, T(1)=1, T(2)=1. These are fixed by the problem definition and require no computation. They initialize our three rolling variables a=0, b=1, c=1.

Iteration for T(3): next = a+b+c = 0+1+1 = 2. Shift: a=1, b=1, c=2. Now a=T(1), b=T(2), c=T(3)=2.

Iteration for T(4): next = 1+1+2 = 4. Shift: a=1, b=2, c=4. Now c=T(4)=4. Iteration for T(5): next = 1+2+4 = 7. Shift: a=2, b=4, c=7. Loop ends. Return c=7. The answer for n=5 is 7, matching the sequence 0,1,1,2,4,7.

Python rolling-variable version: def tribonacci(n: int) -> int: if n == 0: return 0; if n <= 2: return 1; a, b, c = 0, 1, 1; for _ in range(3, n+1): a, b, c = b, c, a+b+c; return c. The tuple assignment a, b, c = b, c, a+b+c evaluates the full right-hand side before any assignment occurs, so the old values of a and b are correctly used in computing a+b+c. Time O(n), space O(1).

Java rolling-variable version: public int tribonacci(int n) { if (n == 0) return 0; if (n <= 2) return 1; int a = 0, b = 1, c = 1; for (int i = 3; i <= n; i++) { int next = a + b + c; a = b; b = c; c = next; } return c; }. In Java the temporary variable next is mandatory because assignment is sequential — without it, a = b would overwrite a before it is added to the sum.

Python memoization version for comparison: from functools import lru_cache; @lru_cache(None); def tribonacci(n: int) -> int: if n == 0: return 0; if n <= 2: return 1; return tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3). This is clean and readable but O(n) space. Both approaches are accepted on LeetCode, and both run O(n) time.

The Tribonacci problem belongs to the linear DP family where each result depends on a fixed window of prior results. Climbing Stairs (LeetCode 70) is the Fibonacci version — each step can be reached from one or two steps back, giving the same two-variable rolling pattern. Min Cost Climbing Stairs (LeetCode 746) adds costs and a min operation but retains the same two-variable rolling structure.

House Robber (LeetCode 198) uses a similar rolling-window DP: each house depends on the results two houses back (since adjacent houses cannot both be robbed). The window is size 2 like Fibonacci, and the rolling-variable technique applies identically. Extending to House Robber II (LeetCode 213) adds a circular constraint handled by two separate passes.

All of these — Climbing Stairs, Min Cost Climbing Stairs, House Robber, Fibonacci, Tribonacci — share the same structural insight: the answer at position n depends only on a small fixed window of previous answers, so you never need to store the full DP array. Recognizing this pattern and applying rolling variables is a reusable skill across many easy-to-medium DP problems.