Welcome back, dear reader. So, in this article, we will learn a new concept related to numbers called CATALAN NUMBERS. Let us first discuss the question.
Important Links : Problem Link, Solution Video
Prev Next
Catalan Numbers
Question Overview:
You are given that the 0th Catalan number is 1 and the first Catalan number is also 1. You have to find the nth Catalan number given that the nth Catalan number can be calculated as shown:
You may refer to the CATALAN NUMBER VIDEO to understand the question if you have any doubts regarding it. So, dear reader, try to solve this problem on your own first and then refer to the solution.
Approach:
Time Complexity: O(n2) where n is the input number..
Space Complexity: O(n)
Algorithm:
- Create a dp array of size n+1 where n is the input Catalan number.
- Fill dp[0]=1 and dp[1]=1 and then start the outer loop from i=2 to i=n.
- Start the inner loop from j=0 to less than I i.e. j=0 to j< i.
- Use the formula dp[i] += dp[j] x dp[i-j-1] inside the inner loop to fill the array with the Catalan numbers.
- Print dp[n] as the answer.
Explanation:
This question is straightforward. Let us start with our first step of solving a typical dynamic programming problem.
- Storage and Meaning:
So, we will create a dp array of size n+1 (as there are n+1 Catalan numbers from 0 to n) and each element of the array will store that indexed Catalan number. (if input n=8 then look at the image shown below)For instance, the element at index 3 will be the third Catalan number C3. - The direction of solving
This is also very simple. We already know the values of the 0th Catalan number and the 1st Catalan number i.e. 1. We have to find the nthCatalan number. So, the problem size increases when we move from 0 to n, and the same will be the direction of solving. - Travel and Solve
So, let us take a look at some of the Catalan numbers that we can derive from the formula above.
Every term comprises multiplication of the two terms. So, if we are calculating the nth Catalan number, the first number in every term starts from index 0 till the index n-1 for n terms.
For instance, if we calculate the 2nd Catalan number, the first number in the first term is C0 and the first number in the last term is C1 i.e. n-1. So, the first number of terms will be from 0 to n-1 Catalan numbers. What about the second term?
Have a look at the image below:
If we number the Catalan terms from 0 to n-1 when we are calculating the nth Catalan number, we see that the ith term in the nth Catalan number is Ci x Cn-i-1.
So, we now know both the numbers in the ith term of a Catalan number. Now, we just have to fill the dp array.
So, by using the above formula, we can easily fill the complete dp array. The dp array filled for n=5 is shown below:
We recommend you refer to the solution video to understand the above filling procedure of the array if you have any doubts about it. However, it is very simple, we just have to apply the Catalan number formula that we have studied above.
To implement the Java Code of this solution, we request you keep in mind the below two points:
- Every Catalan's number (if it is the nth Catalan number) will have total n terms (not 0th and 1st Catalan numbers)
- The ith term in a Catalan number will be a product of two numbers. This can be represented as Ci x Cn-i-1. Here "i" starts from 0 and reaches till n-1 i.e. the terms in a Catalan Number's formula are numbered from 0 to n-1.
So, now that we have studied everything, let us implement the Catalan number code ourselves.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scn=new Scanner(System.in);
int n=scn.nextInt();
long[] dp = new long[n + 1];
dp[0] = 1; //since 0th Catalan number is 1
dp[1] = 1; //since 1st Catalan number is also 1
for(int i = 2; i < dp.length; i++){
for(int j = 0; j < i; j++){
dp[i] += dp[j] * dp[i - 1 - j];
}
}
System.out.println(dp[n]); //nth Catalan number
}
}
java;
true";
We recommend you refer to the solution video once to understand the code written above if you have any doubts regarding it. Now, let us discuss the time and space complexity of this code.
Analysis
Time Complexity:
The time complexity of the above solution is O(n2) where n is the input number. Did you think that the time complexity is O(n)? Well, it is not. This is because the inner loop runs for "i" number of times and the outer loop runs for n times. So, when i=2, the inner loop runs for 2 times, and when i=3, the inner loop runs for 3 times, and so on when i=n, the inner loop runs for n times.
So, the inner loop runs n(n+1)/2 times. Why? Think about this!!! This is what makes the time complexity go O(n2).
O(n)
Space Complexity:
The space complexity is O(n) as we make an array of size n+1.
So, dear reader, we hope that you got the time and space complexity as well. We recommend you refer to the complete solution video once to clear all your doubts if any. With this, we have completed this problem.
Suggestions:
Here are some suggestions from our side that you do not want to miss:
- We recommend you try to find out some of the use cases of the Catalan number in programming from the internet.
- You might think that this was a pretty simple problem and why have we discussed this in level2 and not in foundation. We will be solving a lot of upcoming problems based on Catalan numbers and those will not be direct problems but we will reduce them to Catalan numbers. So, it is not as easy as it seems to be. So, get ready for it. Till then, Happy Coding!!!
