Catalan Numbers

Problem Statement

The n-th Catalan number counts the number of valid expressions, binary search trees, or ways to parenthesize expressions. Compute the n-th Catalan number efficiently.

Example: Input: n = 4, Output: 14 (valid BSTs / valid parentheses sequences)

Approach 1: Recursion

Explanation: Catalan number can be defined recursively: Cn = Σ Ci * Cn-i-1 for i=0..n-1

Time Complexity: O(2n)

Space Complexity: O(n) recursion stack

function catalan(n):
    if n == 0 or n == 1: return 1
    res = 0
    for i = 0 to n-1:
        res += catalan(i) * catalan(n-i-1)
    return res

Approach 2: Memoization (Top-Down DP)

Explanation: Store results of subproblems to avoid recomputation.

Time Complexity: O(n2)

Space Complexity: O(n) recursion stack + O(n) DP array 

dp[0..n] = -1
function catalan(n):
    if n == 0 or n == 1: return 1
    if dp[n] != -1: return dp[n]
    res = 0
    for i = 0 to n-1:
        res += catalan(i) * catalan(n-i-1)
    dp[n] = res
    return res

Approach 3: Tabulation (Bottom-Up DP)

Explanation: Compute all Catalan numbers from 0 to n iteratively.

Time Complexity: O(n2)

Space Complexity: O(n)

dp[0] = dp[1] = 1
for k = 2 to n:
    dp[k] = 0
    for i = 0 to k-1:
        dp[k] += dp[i] * dp[k-i-1]
return dp[n]

Approach 4: Using Binomial Coefficient

Explanation: Catalan(n) = C(2n, n) / (n+1)

Time Complexity: O(n)

Space Complexity: O(1)

function catalan(n):
    return binomialCoefficient(2*n, n) / (n + 1)
Flowchart