Catalan Numbers

Recursive implementation of Catalan Number Generation

One can easily deduce the recurrence formula from the problem of the correct bracket sequence.

Since we have deduced the formula, we can apply and implement this formula using Recursion.

Algorithm

1. We will create a function named solve, which will accept a single parameter, and that will be N.

2. If the value of N becomes less than 1, then we will return 1; this will be our base case.

3. Now, we will loop from 1 to N and add the result in the variable at each iteration.

4. The formula to calculate the result at each iteration would be solve(i) * solve(n - i - 1).

5. In the end, we will return the variable to store the result.

Dry Run

Here in this example, we will draw a recursion tree for N=3, 

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int solve(int n)
{
    // Base case
    if (n <= 1)
        return 1;

    
    int nthCatalan = 0;

     // Applying the formula to find out the nth catalan number
    for (int i = 0; i < n; i++)
    {
        nthCatalan += solve(i) * solve(n - i - 1);
    }

    return nthCatalan;
}

// Driver function.
int main()

{
    int n = 8;

    cout << "The first " << n << " Catalan Numbers are: ";

    for (int i = 0; i < n; i++)
    {
        cout << solve(i) << " ";
    }
    cout << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output

The first 8 Catalan Numbers are: 1 1 2 5 14 42 132 429 

You can also try this code with Online C++ Compiler

Run Code

Complexities

Time complexity

The time complexity is exponential in nature.

Space complexity

The space complexity would be O(n) because of the stack space used by the recursive calls.

As we know, while writing any program, Time and Space Complexity plays a vital role in choosing the algorithm. Therefore we should look for a different approach to generating such Catalan numbers.

Read More - Time Complexity of Sorting Algorithms

Catalan Number generation using Dynamic Programming

Since it is clear that the recursive approach has exponential time complexity, we know that it does a lot of repeated computation (we can do the same by drawing a recursion tree); now, since there are repeated computations, there exist overlapping subproblems, we can apply Dynamic Programming. So to convert the recursive approach into a dynamic programming approach, we will use memoization.

Dry Run

Let us consider this case for N=3, as we already know that the recursion tree looks like the figure given below, 

In this figure, we can see that there are overlapping subproblems, which means that we are computing the same result multiple times (like we are computing the value of N=2 two times), so our time complexity is increasing so to avoid that we will store the result in a dp array (like for N=2, we store the result of N=2 in dp[2]). So after storing the result, the figure will look like this,

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// dp array to store the computed results
int dp[100001];

int solve(int n)
{
    if (n <= 1)
        return 1;

    // checking the result of this number is
    // already stored in the dp array or not
    if (dp[n] != -1)
        return dp[n];

    // applying the formula to find out the nth catalan number
    int nthCatalan = 0;
    for (int i = 0; i < n; i++)
    {
        nthCatalan += solve(i) * solve(n - i - 1);
    }

    // storing the result in the dp array
    return dp[n] = nthCatalan;
}

// Driver function.
int main()

{
    int n = 8;
    memset(dp, -1, sizeof(dp));
    dp[0] = dp[1] = 1;
    solve(n);

    cout << "The first " << n << " Catalan Numbers are: ";

    for (int i = 0; i < n; i++)
    {
        cout << dp[i] << " ";
    }
    cout << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output

The first 8 Catalan Numbers are: 1 1 2 5 14 42 132 429 

You can also try this code with Online C++ Compiler

Run Code

Complexities

Time Complexity

To find the nth Catalan number, the complexity is O(N), but we are finding a series of Catalan numbers, so the overall complexity is O(N²). Since we are using a for loop to calculate the ith Catalan number, and since we need a for loop to calculate every Catalan number, the time complexity would be O(N²).

Space Complexity

Since we have stored the results of every Catalan number in 1d array, space complexity would be O(N).

Catalan Number generation using Binomial Coefficient

To further reduce the time complexity and efficiently calculate Catalan's numbers, we can also use binomial coefficient formulas to find the nth Catalan number in O(n) time ( as discussed in one of the approaches of our problems on Coding Ninjas Studio - link ).

The binomial coefficient, also known as a "choose function," is a mathematical concept that describes the number of possible combinations of k objects from a set of n distinct objects, without regard to the order in which they are chosen. The binomial coefficient is denoted as "n choose k," and is represented mathematically as:

n choose k  or nCk = n! / (k! * (n-k)!)

where "n" and "k" are non-negative integers, and "!" denotes the factorial function (the product of all positive integers up to and including the given integer).

Implementation in C++

#include <iostream>
using namespace std;

unsigned long long factorial(unsigned int n)
{
    unsigned long long ans = 1;
    for (int i = 1; i <= n; i++)
    {
        ans *= i;
    }
    return ans;
}

// Formula = (2n)! / ((n)!x(n+1)!)
unsigned long long solve(unsigned int n)
{
    if (n == 0)
        return 1;
    
    // Calculate (2n)!
    unsigned long long numerator = factorial(2 * n);

    // Calculate n!
    unsigned long long denominator1 = factorial(n);

    // Calculate (n+1)!
    unsigned long long denominator2 = factorial(n + 1);

    // Calculate the result
    return numerator / (denominator1 * denominator2);
}

int main()
{
    int n = 8;

    cout << "The first " << n << " Catalan Numbers are: ";

    for (int i = 0; i < n; i++)
    {
        cout << solve(i) << " ";
    }
    cout << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output

The first 8 Catalan Numbers are: 1 1 2 5 14 42 132 429 

Complexities

Time Complexity

Since we are using a for loop to calculate every Catalan number, the Catalan number is calculated using a formula. The time complexity for calculating the Catalan number is O(N), and we are calculating the Catalan number for a series of N numbers. Therefore overall time complexity is O(N²).

Space Complexity

Since we are not using any data structure to compute the result, the space complexity would be O(1).

We recommend you practice the binomial coefficient problem on Coding Ninjas Studio after knowing all about its approach.

Applications of Catalan Numbers

The different set of problems that can be shown/reduced to be completely equivalent to a problem that has their solutions which is essentially the same as the Catalan number sequence that we learned about, are as follows:

Counting the Mountain Ranges: Number of ways to form "mountain ranges" with n upstrokes and n downstrokes so that they all stay above the original line. 

Balanced Parentheses: Number of correct bracket sequences consisting of n opening and n closing brackets. 

Counting the number of Multiplication Orderings: Suppose you have a set of n+1 numbers to multiply together with n multiplications to perform. We have to perform multiplication without changing the order of numbers; one can multiply the numbers together in different orders. Here are the possible multiplication orderings for 0 ≤ n ≤ 4 multiplications. 

Count rooted Binary Trees with ‘N’ internal nodes: The number of non-isomorphic full binary trees with 'n' internal nodes (i.e., nodes having at least one child).

Frequently Asked Questions

What are Catalan Numbers?

Catalan numbers is a number sequence, which is helpful in counting and several combinatorial problems, often involving recursively defined objects.

What are different strategies to generate Catalan Numbers?

The Catalan numbers can be generated using a recursive, dynamic, and binomial coefficient approach.

What is the time complexity of generating Nth Catalan numbers using the dynamic programming approach?

The dynamic programming approach uses optimal sub-structures and reduces the unnecessary repetitive work while generating Catalan numbers using the recursive method. Therefore the dynamic programming approach reduces the time complexity from exponential order (as obtained in the recursive approach) to O(N^2).

What are some applications of Catalan numbers?

Some of the problems, the solutions of which are equivalent to the Catalan numbers sequence, are, counting mountain ranges, diagonal avoiding paths, counting rooted binary trees with N internal nodes, counting groupings from valid ‘N’ pairs of parenthesis, and many more!!

What is the most efficient method of calculating Catalan numbers?

The most efficient way to calculate the Catalan numbers is using the binomial formula; we can calculate the Catalan numbers in O(N) time complexity.

Also Read - Strong number in c

Conclusion

This article explains Catalan Numbers and how we can leverage them to solve common problems in technical interviews. 

We also saw that there's no need to collect loads of redundant and additional steps while working on strategies to generate Catalan numbers. We can optimize the answer by collecting only the information we need to know using the dynamic programming approach.

We also looked at problems whose solution is the same Catalan numbers sequence we generated.

Apart from that, it would be best if you learned more about our Guided Path for DSA.

Additionally, you can use Coding Ninjas Studio to practice a wide range of DSA tasks typically asked in interview rounds. This will assist you in mastering efficient coding methodologies, with the added benefit of scholar interview experiences in large product-based organizations.

Happy learning!