Catalan Numbers

Problem

Given a non-negative integer n, compute the n-th Catalan number C_n.

What are catalan numbers

Catalan numbers form a sequence of natural numbers with applications in various combinatorial mathematics problems. They can be defined in several ways and appear in problems involving balanced parentheses, binary search trees, and more. More on wiki.

The (n)-th Catalan number can be given by the formula:

$$ C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!} $$

Some common properties of Catalan numbers include:

• They count the number of expressions containing (n) pairs of correctly matched parentheses. See - Generate Parentheses.
• They count the number of rooted binary trees with (n + 1) leaves.
• They count the number of ways to completely parenthesise (n+1) factors in a product.

Examples

Example 1

1
2
3

Input: n = 0
Output: 1
Explanation: Base condition C_0 = 1.

Example 2

1
2
3

Input: n = 3
Output: 5
Explanation: Sequence starts 1, 1, 2, 5, 14, ... so C_3 = 5.

Example 3

1
2
3

Input: n = 5
Output: 42
Explanation: C_5 = 42 (common benchmark value).

Solution

Method 1 - Naive Recursion

Intuition

Directly apply the recursive convolution definition. This recomputes the same substructures many times, causing explosive growth in calls.

Approach

Base: C_0 = 1 (and optionally C_1 = 1). For n > 1 sum over splits (i, n-1-i) multiplying left and right Catalan values.

Recurrence

$$C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$$

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    // Method 1: Naive recursion
    public long catalan(int n) {
        if (n <= 1) return 1L;
        long ans = 0L;
        for (int i = 0; i < n; i++) {
            ans += catalan(i) * catalan(n - 1 - i);
        }
        return ans;
    }
}

1
2
3
4
5
6

class Solution:
    # Method 1: Naive recursion
    def catalan(self, n: int) -> int:
    if n <= 1:
        return 1
    return sum(self.catalan(i) * self.catalan(n - 1 - i) for i in range(n))

Complexity

• ⏰ Time complexity: O(C_n * n) (super-exponential in n; asymptotically C_n ~ 4^n / (n^{3/2}√π)), due to massive recomputation.
• 🧺 Space complexity: O(n) – recursion stack depth.

Method 2 - Top-Down DP (Memoization)

Intuition

Cache intermediate Catalan values so each C_k is computed once; transforms exponential recursion into polynomial time.

Approach

Use an array/map memo with sentinel (e.g. -1 or null). On each call return stored value if present; otherwise compute via recurrence and store.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import java.util.Arrays;
class SolutionMemo { // distinct class name to avoid clash in note
    private long[] memo;
    public long catalan(int n) {
        memo = new long[n + 1];
        Arrays.fill(memo, -1L);
        memo[0] = 1L; if (n >= 1) memo[1] = 1L;
        return solve(n);
    }
    private long solve(int n) {
        if (memo[n] != -1L) return memo[n];
        long ans = 0L;
        for (int i = 0; i < n; i++) ans += solve(i) * solve(n - 1 - i);
        memo[n] = ans;
        return ans;
    }
}

1
2
3
4
5
6
7
8
9

from functools import lru_cache
class SolutionMemo:
    def catalan(self, n: int) -> int:
    @lru_cache(None)
    def solve(k: int) -> int:
        if k <= 1:
        return 1
        return sum(solve(i) * solve(k - 1 - i) for i in range(k))
    return solve(n)

Complexity

• ⏰ Time complexity: O(n^2) – n states, each summation over up to n splits.
• 🧺 Space complexity: O(n) – memo array + recursion stack.

Method 3 - Bottom-Up DP

Intuition

Iteratively build from C_0 upward; avoids recursion overhead and is iterative equivalent of memoized solution.

Approach

Initialize dp[0]=1, dp[1]=1. For each i from 2..n, accumulate dp[i] += dp[j]*dp[i-1-j] for j in [0, i-1].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class SolutionBottomUp {
    public long catalan(int n) {
        long[] dp = new long[n + 1];
        dp[0] = 1L; if (n >= 1) dp[1] = 1L;
        for (int i = 2; i <= n; i++) {
            long cur = 0L;
            for (int j = 0; j < i; j++) cur += dp[j] * dp[i - 1 - j];
            dp[i] = cur;
        }
        return dp[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class SolutionBottomUp:
    def catalan(self, n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = 1
    if n >= 1:
        dp[1] = 1
    for i in range(2, n + 1):
        total = 0
        for j in range(i):
        total += dp[j] * dp[i - 1 - j]
        dp[i] = total
    return dp[n]

Complexity

• ⏰ Time complexity: O(n^2) – double loop over splits.
• 🧺 Space complexity: O(n) – DP array.

Method 4 - Direct Combinatorial Formula

Intuition

Use multiplicative computation of the binomial coefficient to avoid factorial overflow and then divide by n+1.

Approach

Iteratively build res = res * (n+i) / i for i = 1..n to compute binom(2n, n), then C_n = res / (n+1).

Code

1
2
3
4
5
6
7
8

class SolutionFormula {
    public long catalan(int n) {
        if (n <= 1) return 1L;
        long res = 1L; // binom(2n, n)
        for (int i = 1; i <= n; i++) res = res * (n + (long)i) / i;
        return res / (n + 1L);
    }
}

1
2
3
4
5
6
7
8

class SolutionFormula:
    def catalan(self, n: int) -> int:
    if n <= 1:
        return 1
    res = 1
    for i in range(1, n + 1):
        res = res * (n + i) // i  # binom(2n, n)
    return res // (n + 1)

Complexity

• ⏰ Time complexity: O(n) – single loop building binomial.
• 🧺 Space complexity: O(1) – constant auxiliary space.

Method Comparison

Notes

For large n, use big integer arithmetic to prevent overflow. For example, in Java replace long with BigInteger and adjust multiplicative formula accordingly. The DP methods also generalize if you substitute arbitrary semiring operations where Catalan convolution applies.