Log inSign up
mediumGeeksforGeeksNot Started

Catalan Number

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Catalan numbers form a sequence of natural numbers that occur in various counting problems, especially in recursive structures.

The first few Catalan numbers for n = 0, 1, 2, 3, \dots are: $1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \dots$

They satisfy the fundamental recurrence relation: $C_0 = 1, \quad C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i} \quad \text{for } n >= 1$

Given an integer n, return the n-th Catalan number C_n.

### Classic Combinatorial Applications 1. Number of distinct Binary Search Trees (BSTs) that can be formed with n unique keys. 2. Number of valid expressions containing n pairs of parentheses (Dyck words). 3. Number of ways a convex polygon with n + 2 sides can be triangulated. 4. Number of mountain ranges that can be drawn with n upstrokes and n downstrokes.

### Example 1 - Input: n = 3 - Output: 5 - Explanation: For n = 3 keys, exactly 5 unique BSTs can be formed.

### Example 2 - Input: n = 4 - Output: 14

Constraints:

  • 0 <= n <= 30 (for 64-bit integer limits)
  • Catalan numbers grow as O(4n / (n^(3/2) * sqrt(pi)))

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Derive the Catalan recurrence from root partitioning in trees and parentheses matching.
  • Implement the O(n2) DP convolution table.
  • Optimize to O(n) time and O(1) space using the iterative ratio formula.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Counting valid parentheses expressions, distinct BST structures, full binary trees, or non-crossing chords.
  • Splitting a structure around a root/pivot where left and right parts are independent sub-structures.

Algorithmic Decision Tree:

  • If recurrence involves sum of products C_i * C_{n-1-i} -> Catalan Number sequence.
  • Use BigInt or 64-bit integers to prevent overflow.

Connected Patterns:

Unique Binary Search TreesGenerate ParenthesesMatrix Chain Multiplication

1. Pure Recursive Summation

Intuition

Directly apply the formula C_n = sum_{i=0}^{n-1} C_i * C_{n-1-i} using naive recursion.

Algorithm

  1. Base Case: If n <= 1, return 1.
  2. Initialize res = 0.
  3. For i from 0 to n - 1:
  4. res += catalan(i) * catalan(n - 1 - i).
  5. Return res.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5long long catalanRecursive(int n) {
6 if (n <= 1) return 1;
7 long long res = 0;
8 for (int i = 0; i < n; i++) {
9 res += catalanRecursive(i) * catalanRecursive(n - 1 - i);
10 }
11 return res;
12}
13
14int main() {
15 int n = 4;
16 cout << "Catalan(" << n << ") [Recursive]: " << catalanRecursive(n) << endl;
17 return 0;
18}

Time & Space Complexity

  • Time complexity: O(4^n / n^(3/2))
  • Space complexity: O(n) recursion stack

2. Dynamic Programming Tabulation

Intuition

Build an array dp of size n + 1 where dp[j] = sum_{i=0}^{j-1} dp[i] * dp[j - 1 - i].

Algorithm

  1. Create array dp of size n + 1 filled with 0.
  2. dp[0] = 1, dp[1] = 1.
  3. For j = 2 to n:
  4. For i = 0 to j - 1:
  5. dp[j] += dp[i] * dp[j - 1 - i].
  6. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6long long catalanDP(int n) {
7 if (n <= 1) return 1;
8 vector<long long> dp(n + 1, 0);
9 dp[0] = 1;
10 dp[1] = 1;
11
12 for (int j = 2; j <= n; j++) {
13 for (int i = 0; i < j; i++) {
14 dp[j] += dp[i] * dp[j - 1 - i];
15 }
16 }
17 return dp[n];
18}
19
20int main() {
21 int n = 4;
22 cout << "Catalan(" << n << ") [DP Table]: " << catalanDP(n) << endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n) for dp table

3. Analytical Ratio Formula O(n) Time & O(1) Space

Intuition

Compute Catalan numbers iteratively using the ratio relation C_k = C_{k-1} × \frac{2(2k - 1)}{k + 1}.

Algorithm

  1. Initialize c = 1.
  2. For k = 1 to n:
  3. c = c * 2 * (2 * k - 1) / (k + 1).
  4. Return c.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5long long catalanOptimal(int n) {
6 if (n <= 1) return 1;
7 long long c = 1;
8 for (int k = 1; k <= n; k++) {
9 c = c * 2 * (2 * k - 1) / (k + 1);
10 }
11 return c;
12}
13
14int main() {
15 int n = 4;
16 cout << "Catalan(" << n << ") [Optimal O(n)]: " << catalanOptimal(n) << endl;
17 return 0;
18}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive SumO(4^n / n^(3/2))O(n)Mathematical recurrence implemented with recursion.Redundant sub-computations
2.DP TabulationO(n^2)O(n)Convolution sum filled in 1D array.Inner convolution loop
3.Analytical RatioOptimalO(n)O(1)Iterate closed form ratio C_k = C_{k-1} * 2(2k-1) / (k+1).64-bit integer limit for n > 35

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Dividing before multiplying in the ratio formula: In integer arithmetic, c / (k + 1) * 2 * (2 * k - 1) will truncate to zero prematurely.

Pitfall 2:

Forgetting n = 0 is 1.

Crucial Edge Cases to Validate:

  • n = 0: Output is 1 (empty tree / empty string is 1 valid structure).
  • n = 1: Output is 1.
  • Large n: Integer overflow occurs beyond n = 35 for 64-bit integers; BigInt or modulo arithmetic is required.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Memorize the 4 main appearances of Catalan numbers: Unique BSTs, Valid Parentheses, Polygon Triangulations, Mountain Ranges.
  2. Derive the recurrence dynamically from the BST perspective first, then share the O(n) formula.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the number of unique Binary Search Trees (BSTs) with n keys equal the n-th Catalan number?

Back to DSA Sheet