algoadvance

Leetcode 96. Unique Binary Search Trees

Problem Statement

Given an integer n, return the number of structurally unique Binary Search Trees (BSTs) that store values 1 to n.

Clarifying Questions

1. Range of n: What is the maximum value of n we need to consider?
   • Generally, n will be within the range [1, 19].
2. Output type: Can we assume the result will be a non-negative integer within typical constraints of the int type in C++?
   • Yes.
3. Constraints:
   • 1 <= n <= 19.

Strategy

We can solve this problem using Dynamic Programming. The key insight is to use the concept of Catalan numbers, which count the number of BST configurations.

Steps:

1. Initialize a DP array: Create an array dp where dp[i] represents the number of unique BSTs that can be formed with i nodes.
2. Base Cases:
   • dp[0] = 1 (An empty tree).
   • dp[1] = 1 (A single node tree).
3. Filling the DP Array:
   • For each number of nodes i from 2 to n, compute dp[i] using previously computed values:
     • For each j from 1 to i, treat j as the root.
     • The left subtree would have j-1 nodes and the right subtree would have i-j nodes.
     • Therefore, dp[i] = sum(dp[j-1] * dp[i-j]) for all j in range [1, i].
4. Return dp[n]: The result is stored in dp[n].

Code

#include <vector>

class Solution {
public:
    int numTrees(int n) {
        std::vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
};

Time Complexity

• Time Complexity: (O(n^2))
  • We have a double loop: the outer loop runs from 2 to n (i.e., O(n)), and the inner loop (which calculates the sum) also runs up to n (nested O(n)).
• Space Complexity: (O(n))
  • We use an array dp of size n+1.

This approach is efficient and manageable within the provided constraints.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?