What

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 Problem.
  • 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.

Application of Catalan Number Algorithm

  1. The number of ways to stack coins on a base row of (n) consecutive coins in a plane, where no coins can be placed on the two sides of the bottom row and every additional coin must lie above two other coins, is given by the (n)th Catalan number.
  2. The number of ways to correctly group a string of (n) pairs of parentheses, ensuring each open parenthesis matches with a closing one, corresponds to the (n)th Catalan number.
  3. The number of ways to divide a convex polygon with (n+2) sides into triangles by drawing non-intersecting, straight lines between vertices is determined by the (n)th Catalan number, an application that interested Euler.

Solution

Method 1 - Recursion

Just follow the recursive definition of Catalan numbers: $$ C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i} $$

Code

Java
public class CatalanNumbers {
    public static int catalanRecursive(int n) {
        if (n <= 1) {
            return 1;
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            result += catalanRecursive(i) * catalanRecursive(n - 1 - i);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(catalanRecursive(5)); // Output: 42
    }
}

Complexity

  • ⏰ Time complexity: O(2^n), because each call to catalanRecursive(n) involves two calls for lower values.
  • 🧺 Space complexity: O(n), assuming recursion stack.

Method 2 - Top Down DP

To improve the efficiency, we can use memoization to store the results of previously computed Catalan numbers:

Code

Java
public class CatalanNumbersMemoization {
    private static Map<Integer, Integer> memo = new HashMap<>();

    public static int catalanMemo(int n) {
        if (n <= 1) {
            return 1;
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            result += catalanMemo(i) * catalanMemo(n - 1 - i);
        }
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(catalanMemo(5)); // Output: 42
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), because for each n, the function iterates through i from 0 to n-1.
  • 🧺 Space complexity: O(n), assuming recursion stack and also using memo map

Method 3 - Bottom UP DP

A bottom-up approach avoids the overhead of recursion and is generally more efficient.

Code

Java
public class CatalanNumbersDP {
    public static int catalanDP(int n) {
        int[] dp = new int[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];
    }

    public static void main(String[] args) {
        System.out.println(catalanDP(5)); // Output: 42
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), because of nested loops
  • 🧺 Space complexity: O(n), for using dp array.