Day 19 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/number-of-bst-from-array/1

Number of BST From Array

Difficulty: Hard Accuracy: 87.55%

You are given an integer array arr[] containing distinct elements.
Your task is to return an array where the ith element denotes the number of unique BSTs formed when arr[i] is chosen as the root.
Examples :
Input: arr[] = [2, 1, 3]
Output: [1, 2, 2]

Explanation:

Input: arr[] = [2, 1]
Ouput: [1, 1]
Constraints:
1 ≤ arr.size() ≤ 6
1 ≤ arr[i] ≤ 15

Solution:
class Solution:
def countBSTs(self, arr):

    def num_bsts(n):
        return comb(2 * n, n) // (n + 1)
    arr_sorted = sorted(arr)
    n = len(arr)

    catalan = [num_bsts(i) for i in range(n + 1)]

    result = []
    for x in arr:
        idx = arr_sorted.index(x)
        left = idx              
        right = n - idx - 1  
        result.append(catalan[left] * catalan[right])

    return result