Number of BST From Array

JavaView on GFG

Time: O(n^3)

Space: O(n^2)

Intuition

Count structurally unique BSTs from given array. Sort array; count depends only on subtree sizes.

Algorithm

1After sorting, this equals Catalan number C(n) = C(2n,n)/(n+1). Or DP: dp[n] = sum(dp[i]*dp[n-1-i]).

Common Pitfalls

•Unique BSTs from n distinct values = nth Catalan number. Same as LC 96.

Number of BST From Array.java

Java

// Approach: Catalan number-based DP. dp[i][j] = number of BSTs from arr[i..j] using each element as root.
// Time: O(n^3) Space: O(n^2)
import java.util.*;

class Solution {
    public ArrayList<Integer> countBSTs(int[] arr) {
        ArrayList<Integer> ans = new ArrayList<>();

        for (int x : arr) {
            int less = countLess(arr, x);
            int more = countMore(arr, x);
            ans.add(findCatalan(less) * findCatalan(more));
        }

        return ans;
    }

    private static int mem[] = new int[30];

    private static int findCatalan(int n) {
        if (n <= 1)
            return 1;

        if (mem[n] != 0)
            return mem[n];

        int res = 0;

        for (int i = 0; i < n; i++)
            res += findCatalan(i) * findCatalan(n - i - 1);

        return mem[n] = res;
    }

    private int countLess(int arr[], int x) {
        int c = 0;
        for (int e : arr) {
            if (e < x)
                c++;
        }

        return c;
    }

    private int countMore(int arr[], int x) {
        int c = 0;
        for (int e : arr) {
            if (e > x)
                c++;
        }

        return c;
    }
}

Was this solution helpful?