N-th Tribonacci Number

NeetCode: N-th Tribonacci Number · LeetCode: 1137. N-th Tribonacci Number · Difficulty: Easy

The Tribonacci sequence is defined by T(0) = 0, T(1) = 1, T(2) = 1 and T(n) = T(n-1) + T(n-2) + T(n-3) for n >= 3. Given n, return T(n). The answer is guaranteed to fit in a 32-bit integer (0 <= n <= 37).

Example

Text

Input:  n = 4     Output: 4     (0, 1, 1, 2, 4)
Input:  n = 25    Output: 1389537

Brute force: plain recursion

Translate the definition directly. T(n) calls three smaller values and the calls overlap: T(n-2) is computed again inside T(n-1) and inside T(n). The call tree grows by a factor of about 1.84 per level, so the running time is exponential.

Java

class Solution {
    public int tribonacci(int n) {
        switch (n) {
            case 0:
                return 0;
            case 1:
            case 2:
                return 1;
            default:
                return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.tribonacci(4));
        System.out.println(solution.tribonacci(25));
        System.out.println(solution.tribonacci(0));
    }
}

Output

4
1389537
0

Time: O(1.84^n) (exponential). Space: O(n) for the recursion stack.

Better: memoization

Each T(k) needs to be computed only once. Store finished results in an int array and look them up before recursing. A new int array holds 0, which is a real value (T(0)), so Arrays.fill sets every slot to -1 to mark "not computed yet". There are n + 1 distinct subproblems, each doing constant work.

Java

import java.util.Arrays;

class Solution {
    private int trib(int n, int[] memo) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        if (memo[n] != -1) {
            return memo[n];
        }
        int v = trib(n - 1, memo) + trib(n - 2, memo) + trib(n - 3, memo);
        memo[n] = v;
        return v;
    }

    public int tribonacci(int n) {
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1); // every real value is >= 0, so -1 marks "not computed yet"
        return trib(n, memo);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.tribonacci(4));
        System.out.println(solution.tribonacci(25));
        System.out.println(solution.tribonacci(0));
    }
}

Output

4
1389537
0

Time: O(n). Space: O(n) for the table and the recursion stack.

Optimal: three rolling variables

Each value depends only on the previous three, so the table is unnecessary. Keep a window (a, b, c) = (T(i-2), T(i-1), T(i)) and slide it forward n times.

Java

class Solution {
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        int a = 0;
        int b = 1;
        int c = 1;
        for (int i = 2; i < n; i++) {
            int next = a + b + c;
            a = b;
            b = c;
            c = next;
        }
        return c;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.tribonacci(4));
        System.out.println(solution.tribonacci(25));
        System.out.println(solution.tribonacci(0));
        System.out.println(solution.tribonacci(1));
        System.out.println(solution.tribonacci(37));
    }
}

Output

Time: O(n). Space: O(1).

For n = 4 the window moves (0,1,1) -> (1,1,2) -> (1,2,4), and c = 4 is the answer. T(37) is 2082876103, which is below Integer.MAX_VALUE, so int is enough for the whole input range. The early return for n == 0 is needed because the loop body does not run for n = 0, and c would then hold T(2).