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];
}
};
Difficulty
and has an acceptance rate of about 63% (1+ million submissions).
Typical patterns to solve this problem:
- Dynamic Programming
- Math
- Memoization
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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 |
Videos
Similar Problems
- problem 509: Fibonacci Number
Solved On The Same Day
- problem 13: Roman to Integer
- problem 21: Merge Two Sorted Lists
- problem 28: Find the Index of the First Occurrence in a String
- problem 35: Search Insert Position
- problem 58: Length of Last Word
- problem 66: Plus One
- problem 67: Add Binary
- problem 69: Sqrt(x)
- problem 70: Climbing Stairs
- problem 206: Reverse Linked List
- problem 242: Valid Anagram
- problem 278: First Bad Version
- problem 283: Move Zeroes
- problem 367: Valid Perfect Square
- problem 374: Guess Number Higher or Lower
- problem 389: Find the Difference
- problem 441: Arranging Coins
- problem 459: Repeated Substring Pattern
- problem 509: Fibonacci Number
- problem 657: Robot Return to Origin
- problem 682: Baseball Game
- problem 704: Binary Search
- problem 709: To Lower Case
- problem 744: Find Smallest Letter Greater Than Target
- problem 746: Min Cost Climbing Stairs
- problem 860: Lemonade Change
- problem 896: Monotonic Array
- problem 976: Largest Perimeter Triangle
- problem 1232: Check If It Is a Straight Line
- problem 1275: Find Winner on a Tic Tac Toe Game
- problem 1351: Count Negative Numbers in a Sorted Matrix
- problem 1491: Average Salary Excluding the Minimum and Maximum Salary
- problem 1502: Can Make Arithmetic Progression From Sequence
- problem 1523: Count Odd Numbers in an Interval Range
- problem 1539: Kth Missing Positive Number
- problem 1572: Matrix Diagonal Sum
- problem 1672: Richest Customer Wealth
- problem 1768: Merge Strings Alternately
- problem 1822: Sign of the Product of an Array
- problem 2: Add Two Numbers
- problem 5: Longest Palindromic Substring
- problem 33: Search in Rotated Sorted Array
- problem 34: Find First and Last Position of Element in Sorted Array
- problem 43: Multiply Strings
- problem 50: Pow(x, n)
- problem 54: Spiral Matrix
- problem 62: Unique Paths
- problem 63: Unique Paths II
- problem 64: Minimum Path Sum
- problem 73: Set Matrix Zeroes
- problem 74: Search a 2D Matrix
- problem 120: Triangle
- problem 139: Word Break
- problem 153: Find Minimum in Rotated Sorted Array
- problem 198: House Robber
- problem 221: Maximal Square
- problem 275: H-Index II
- problem 279: Perfect Squares
- problem 300: Longest Increasing Subsequence
- problem 436: Find Right Interval
- problem 445: Add Two Numbers II
- problem 528: Random Pick with Weight
- problem 540: Single Element in a Sorted Array
- problem 611: Valid Triangle Number
- problem 658: Find K Closest Elements
- problem 852: Peak Index in a Mountain Array
- problem 981: Time Based Key-Value Store
- problem 1041: Robot Bounded In Circle
- problem 1146: Snapshot Array
- problem 2300: Successful Pairs of Spells and Potions
- problem 154: Find Minimum in Rotated Sorted Array II
Extra
- 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