Problem 1137

Abstract / Summary

The task is to compute the n-th number in a sequence where each number is the sum of the three preceding numbers starting from 0 0 1.

Note

The full problem description, including helpful examples, can be found on LeetCode.

C++ 1137.cpp

class Solution {
public:
    int tribonacci(int n) {
        int t[50] = { 0 };
        t[1] = 1;
        t[2] = 1;

        for (int i = 3; i <= n; i++)
            t[i] = t[i-1] + t[i-2] + t[i-3];

        return t[n];
    }
};
13 lines | 243 bytes | submitted August 7, 2023 | GitHub   tab size 4

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 63% (1+ million submissions).

Typical patterns to solve this problem:
  • Dynamic Programming
  • Math
  • Memoization
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation computes the n-th Tribonacci number using an iterative dynamic-programming approach. A Tribonacci sequence extends the Fibonacci concept: each term is the sum of the three preceding terms, with the first three values defined as 0, 1, and 1. The function tribonacci receives a non-negative integer n and returns the corresponding sequence value.

Initialization of the Working Array

The algorithm begins by allocating a fixed-size integer array t with 50 elements, all initialized to zero. This array serves as a table to store intermediate Tribonacci values, allowing later terms to be built from previously computed results.

int t[50] = { 0 };

The explicit zero-initialization guarantees that t[0] holds the correct base value for the sequence without requiring an additional assignment.

Setting Base Cases

The next two statements establish the known starting values of the Tribonacci series. By assigning t[1] and t[2] to 1, the function defines the first three terms of the sequence: t[0] = 0, t[1] = 1, and t[2] = 1. These assignments enable the loop that follows to compute any higher index solely from the table.

t[1] = 1;
t[2] = 1;

Iterative Construction of Subsequent Terms

The core of the algorithm is a for loop that iterates from index 3 up to and including n. In each iteration, the current entry t[i] is calculated as the sum of the three immediately preceding entries. This direct translation of the Tribonacci recurrence eliminates the overhead of recursive calls and ensures that each value is computed exactly once.

for (int i = 3; i <= n; i++)
    t[i] = t[i-1] + t[i-2] + t[i-3];

Because the loop condition uses i <= n, the algorithm naturally handles the situation where n is less than 3: the loop body is skipped, and the function proceeds to return the pre-filled base value.

Returning the Result

After the table has been populated up to the requested index, the function returns the value stored at t[n]. This final step delivers the exact Tribonacci number requested by the caller.

return t[n];

Edge Cases Handled by the Code

When n equals 0, the array entry t[0] remains at its initial zero value, and the function returns 0, matching the definition of the sequence. For n equal to 1 or 2, the earlier base-case assignments ensure that t[1] and t[2] contain the correct value of 1, which the function returns directly. The loop does not execute for these inputs, so no out-of-bounds access occurs.

The fixed array size of 50 also implicitly caps the maximum permissible n. Within typical problem constraints (often n ≤ 37 for 32-bit integers), the array comfortably accommodates all required indices, preventing overflow of the array bounds.

Performance Optimizations Observed

The implementation avoids recursion, thereby eliminating the exponential call overhead associated with naïve recursive definitions of the Tribonacci sequence. By storing each computed term in a pre-allocated array, the algorithm achieves constant-time access to previously calculated values, enabling a straightforward linear progression through the sequence.

Using a static array of a modest, compile-time size eliminates dynamic memory allocation, which reduces runtime overhead and improves cache locality. The loop body consists of a single arithmetic expression, allowing the compiler to generate efficient machine code with minimal instruction count.

Overall, the design balances simplicity with effective use of memory and CPU resources, delivering a fast and reliable computation of Tribonacci numbers for the supported range of inputs.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a long row of empty treasure boxes lined up on the floor. Each box is going to hold a special number, and you want to fill them up one by one following a magic rule. First, you put a zero in the first box, a one in the second box, and another one in the third box. To find out what goes in any other box, you look at the three boxes right before it and add all those numbers together. You keep doing this over and over again, walking down the row and filling each box based on the ones you just finished. By the time you reach the box with the number you are looking for, you will have added everything up just right to find the secret answer hidden inside.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 7.04 | σ = 1.20

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java Python JS Go PHP TS
Progiez C++ Java Python
github BigEggStudy C#
black-shadows C++
chandansgowda Python
charles-wangkai Java
Dijkstra-Edu Java
DimitrisJim C
everthis JS
fartem Ruby
fpdjsns C++
fsq C++
halfrost Go
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
muhammadfarhankt Go
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vthwang Java
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, JavaScript, PHP, Python, TypeScript
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
chandansgowda Python
charles-wangkai Java
Dijkstra-Edu Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fpdjsns C++
fsq C++
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
muhammadfarhankt Go
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vthwang Java
37 links | 24 authors | 10 languages

Videos

8 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

39 easy 31 medium 1 hard
72 solutions   August 7, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality