In this post, we are going to find n-th Catalan number for any given n. There are 3 solutions. They are iteration, recursion and dynamic programming.


Table of content


Iterative solution

This solution is applying the following alternative expression of Cn. It can be implemented with iteration. It has the best time complexity O(n).

catalan number formula 2

Java

Javascript

Python


Recursive solution

This solution is using the another alternative expression of Cn. It can be implemented with recursion. It has the worst time complexity O(2^n) with repeated calls.

catalan number formula 1

Java

Javascript

Python

Doodle

catalan number recursion


Dynamic programming

This solution uses the same expression as recursion. But it overcomes the overlapping in recursion by using dynamic programming technique tabulation. The result from previous calls are saved to a 2d array. They can be re-used for the following steps without calling the recursion. It improves the time complexity from exponential to O(n^2).

Java

Javascript

Python


Download

Download Catalan number in Java, JavaScript and Python
View how to find nth Catalan number in recursion
Numbers and recursions doodle compilation(YouTube)

Can you explain Catalan number in two sentences?

catalan number formula 3

Catalan number follows the formula of (2n)!/(n+1)!n!. The first few Catalan numbers for n = 0, 1, 2, 3, … are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …  

What is Catalan number used for?

catalan logo

Catalan numbers occur in many counting problems in combinatorics, such as count the number of ways to generate n pairs of valid parentheses, count the number of full binary trees with n+1 leaves.