N-th Tribonacci Number

Q: What is the time complexity of N-th Tribonacci Number?

O(n). The algorithm iterates from 3 to n once, performing constant-time operations per iteration, resulting in linear time complexity.

Q: What pattern does N-th Tribonacci Number use?

The Pattern: Dynamic Programming (Iterative State Compression) The Heuristic: When a linear recurrence depends only on a fixed number of previous states, maintain just those states in variables and iteratively update them to achieve O(1) space and O(n) time.

Easy Dynamic Programming

Problem

Given an integer n, return the n-th Tribonacci number where T0 = 0, T1 = 1, T2 = 1, and Tn = Tn-1 + Tn-2 + Tn-3 for n >= 3.

0 ≤ n ≤ 37

Example

Input: n = 4

Output: 4

The Tribonacci sequence starts as 0, 1, 1, 2, 4, ... For n=4, the value is T3 + T2 + T1 = 2 + 1 + 1 = 4. The algorithm handles base cases directly and iteratively computes subsequent values by summing the previous three.

Approach

Straightforward Solution

A naive recursive solution directly implements the recurrence but results in exponential time due to repeated calculations of the same subproblems.

Core Observation

The Tribonacci number at position n depends solely on the sum of the three preceding numbers, forming a linear recurrence relation with fixed base cases.

Path to Optimal

Recognizing the overlapping subproblems and optimal substructure, the problem is suited for dynamic programming. Instead of recursion, an iterative approach with constant space tracks only the last three computed values, enabling efficient computation.

Optimal Approach

Use three variables to store the last three Tribonacci numbers and iteratively update them from 3 up to n. This approach achieves O(n) time and O(1) auxiliary space, directly computing the n-th Tribonacci number without recursion or extra memory.

Time

O(n)

The algorithm iterates from 3 to n once, performing constant-time operations per iteration, resulting in linear time complexity.

Space

O(1)

Only three variables are used to store intermediate Tribonacci values, so the auxiliary space is constant regardless of input size.

Pattern Spotlight

Dynamic Programming (Iterative State Compression)

When a linear recurrence depends only on a fixed number of previous states, maintain just those states in variables and iteratively update them to achieve O(1) space and O(n) time.

Solution

Python

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

Step-by-Step Solution

Return Base Cases Directly for n = 0, 1, or 2

3if n == 0:
4    return 0
6if n <= 2:
7    return 1

Objective

To handle the trivial cases where the Tribonacci number is known without iteration.

Key Insight

The first three Tribonacci numbers are fixed and defined explicitly. Returning these values immediately avoids unnecessary computation and simplifies the iterative logic by ensuring n >= 3 for the loop.

Interview Quick-Check

Core Logic

Directly returning known base cases prevents redundant computation and sets clear boundaries for the iterative process.

State & Boundaries

The conditions `n == 0` and `n <= 2` partition the input domain into base cases and the iterative case.

Common Pitfalls & Bugs

Failing to handle base cases separately can cause index errors or incorrect results in the iterative loop.

Iteratively Compute Tribonacci Numbers Using Rolling Variables

To compute the n-th Tribonacci number by iteratively summing the previous three values and updating state variables.

Return the Computed n-th Tribonacci Number

To output the final computed Tribonacci number after completing the iteration.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 14 Critical

next_value = a + b + c

Calculate the next Tribonacci number as the sum of the previous three.

This line implements the core recurrence relation, which defines the Tribonacci sequence.

Line 19 Critical

return c

Return the computed n-th Tribonacci number stored in c.

After completing the iteration, `c` holds the correct Tribonacci number for n, making it the correct return value.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why is it sufficient to store only the last three Tribonacci numbers when computing the n-th number?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct N-th Tribonacci Number from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the N-th Tribonacci Number drill

or drill a free problem

1	`class Solution:`
2	`def tribonacci(self, n: int) -> int:`
3	`if n == 0:`
4	`return 0`
5
6	`if n <= 2:`
7	`return 1`
8
9	`a = 0`
10	`b = 1`
11	`c = 1`
12
13	`for _ in range(3, n + 1):`
14	`next_value = a + b + c`
15	`a = b`
16	`b = c`
17	`c = next_value`
18
19	`return c`

3	`if n == 0:`
4	`return 0`
6	`if n <= 2:`
7	`return 1`