Leetcode – N-th Tribonacci Number Solution

Spread the love

The “N-th Tribonacci Number” problem on Leetcode is a captivating computational problem that challenges you to implement a Tribonacci sequence generator. The Tribonacci sequence is an extension of the well-known Fibonacci sequence but with a slight twist. Instead of each number being the sum of its two preceding ones, each number in a Tribonacci sequence is the sum of its three preceding numbers.

In this comprehensive article, we’ll explore the problem statement, dissect multiple approaches to solve this problem, and evaluate their respective time and space complexities.

Problem Description

The problem statement from Leetcode is as follows:

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Example:

Input: n = 4
Output: 4

Naive Recursive Approach

The first and most straightforward approach to solve this problem is to use recursion. This naive approach calculates the n-th Tribonacci number using the formula Tn+3 = Tn + Tn+1 + Tn+2.

Here’s how this would look in Python:

def tribonacci(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        return tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3)

Time Complexity:

The time complexity of this approach is O(3^n), making it inefficient for large n.

Space Complexity:

The space complexity is O(n) due to recursion stack space.

Dynamic Programming (Memoization)

To improve the naive recursive approach, you can use dynamic programming with memoization to store previously computed Tribonacci numbers and reuse them.

def tribonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    memo[n] = tribonacci(n-1, memo) + tribonacci(n-2, memo) + tribonacci(n-3, memo)
    return memo[n]

Time Complexity:

The time complexity now improves to O(n).

Space Complexity:

The space complexity remains O(n) due to memoization and recursion stack.

Dynamic Programming (Bottom-up Approach)

We can further optimize the code using a bottom-up approach, eliminating the need for recursion.

def tribonacci(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    
    trib = [0, 1, 1]
    for i in range(3, n+1):
        trib.append(trib[i-1] + trib[i-2] + trib[i-3])
    
    return trib[n]

Time Complexity:

The time complexity remains O(n).

Space Complexity:

The space complexity is O(n) for storing the Tribonacci numbers in an array.

Dynamic Programming (Optimized Space)

If you observe closely, you’ll notice that we don’t need to store all the Tribonacci numbers. We only need the last three numbers to calculate the next one. This enables us to optimize the space complexity.

def tribonacci(n):
    if n == 0:
        return 0
    elif n == 1 or 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

Time Complexity:

The time complexity is O(n).

Space Complexity:

The space complexity is O(1), as we only need to store three variables.

Conclusion

The “N-th Tribonacci Number” problem is an exciting challenge that builds on the foundation of sequence generation algorithms. It provides an excellent opportunity to understand and implement dynamic programming approaches in Python. While the naive recursive approach is simple to understand, it lacks efficiency. The optimized dynamic programming approach offers a perfect blend of time and space efficiency.

This problem serves as a robust test for both your algorithmic skills and your Python programming prowess. Whether you’re preparing for an interview, a coding competition, or just looking to learn, this problem is a must-solve.

Leave a Reply