Program for nth Catalan Number

Problem Statement

Find the nth Catalan Number. Catalan numbers form the sequence: 1, 1, 2, 5, 14, 42, 132, ... and appear in many counting problems like the number of valid parentheses combinations, number of BSTs with n keys, etc.

Example:

• Input: n = 5
• Output: 42 (the 5th Catalan number)

Noob-Friendly Explanation

Imagine you have pairs of parentheses and you want to know how many valid ways you can arrange them. For 3 pairs: ((())), (()()), (())(), ()(()), ()()() — that's 5 ways, which is the 3rd Catalan number! Catalan numbers pop up everywhere in math — counting trees, paths, polygons, and more. The formula is: C(n) = sum of C(i) × C(n-1-i) for i from 0 to n-1.

Approach 1: Brute Force (Recursion)

Intuition

Use the recursive definition directly: C(0) = C(1) = 1, and C(n) = Σ C(i) × C(n-1-i) for i = 0 to n-1. This leads to a lot of repeated calculations.

Algorithm

1. Base case: if n ≤ 1, return 1
2. Sum up C(i) × C(n-1-i) for all i from 0 to n-1

public class Solution {
    public long catalan(int n) {
        if (n <= 1) return 1;

        long result = 0;
        for (int i = 0; i < n; i++) {
            result += catalan(i) * catalan(n - 1 - i);
        }

        return result;
    }
}

Complexity Analysis

• Time Complexity: O(3^n) - The recursion tree grows exponentially (similar to Catalan number growth)
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Optimal (Bottom-Up DP)

Intuition

Store previously computed Catalan numbers in an array so we never recompute them. Build from C(0) up to C(n).

Algorithm

1. Create array dp of size n + 1
2. Set dp[0] = dp[1] = 1
3. For each i from 2 to n, compute dp[i] = Σ dp[j] × dp[i-1-j] for j = 0 to i-1
4. Return dp[n]

public class Solution {
    public long catalan(int n) {
        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = 1;

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

        return dp[n];
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - Two nested loops
• Space Complexity: O(n) - Array to store n + 1 Catalan numbers