algoadvance

Leetcode 1137. N

Problem Statement

The Tribonacci sequence T(n) is defined as follows:

T(0) = 0, T(1) = 1, T(2) = 1, and T(n+3) = T(n) + T(n+1) + T(n+2) for n >= 0.

Given n, return the value of T(n).

Clarifying Questions

  1. Input Constraints: What is the range of the input value n?
    • Typically, the constraints allow for 0 <= n <= 37, as larger values might require more optimized approaches.
  2. Output Format: What should be the output format?
    • The output should be a single integer representing the Tribonacci number T(n).

Strategy

To solve this problem efficiently, we can use dynamic programming. Specifically, we can build the Tribonacci sequence iteratively from the base cases up to n. This avoids the exponential time complexity of a naive recursive implementation.

  1. Initialization: We will initialize the first three values of the Tribonacci sequence: T(0), T(1), and T(2).
  2. Iteration: We will iterate from 3 to n and use the known values T(i) = T(i-1) + T(i-2) + T(i-3).
  3. Space Optimization: Since we only need the last three computed values at any time, we can optimize the space complexity by using three variables instead of an array.

Code

Here is the C++ implementation of the above strategy:

#include <iostream>
using namespace std;

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        
        int t0 = 0, t1 = 1, t2 = 1;
        int t3;
        
        for (int i = 3; i <= n; ++i) {
            t3 = t0 + t1 + t2;
            t0 = t1;
            t1 = t2;
            t2 = t3;
        }
        return t3;
    }
};

// Example usage
int main() {
    Solution solution;
    int n = 25;  // Example input
    cout << "T(" << n << ") = " << solution.tribonacci(n) << endl;
    return 0;
}

Time Complexity

The time complexity of this solution is O(n) because we compute each value of the Tribonacci sequence up to n exactly once.

Space Complexity

The space complexity of this solution is O(1) due to the optimization where only a constant amount of extra space is used for the three variables tracking the last three Tribonacci numbers.

This approach ensures both efficiency and clarity, making it suitable for typical constraints on LeetCode.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI