Nth Catalan Number

Catalan numbers are one of the most famous sequences in combinatorics: 1, 1, 2, 5, 14, 42, … They count a surprising number of things — the number of binary search trees you can build from n nodes, the number of ways to balance n pairs of parentheses, the number of ways to triangulate a polygon, and many more. This problem asks you to compute the nth one.

The slow way first

The textbook definition is recursive: to get C[k], sum C[i] * C[k-1-i] over every split point i. Translated directly into a recursive function with no memo, that recomputes the same smaller Catalan numbers over and over — the call tree explodes exponentially, the same trap as naive Fibonacci.

The question to ask: which smaller values does C[k] depend on? Only C0 through C[k-1]. So if I compute them in order and store each one, every term I need is already sitting in a table.

The idea: build the table bottom-up

Make an array dp where dp[k] will hold C[k]. Seed dp[0] = 1. Then fill dp[1], dp[2], … in order. For each k, walk a split index i from 0 to k-1 and add dp[i] * dp[k-1-i] to a running total. The two factors are a symmetric pair: as i moves right from the front, k-1-i moves left from the back, and they sweep toward the middle.

The key insight: every C[k] is a sum over all the ways to split into a left part of size i and a right part of size k-1-i. That is exactly why Catalan numbers count binary search trees — pick a root, and the left and right subtrees are independent smaller problems.

Walk through it

Step through the animation. The cells hold C0..C4. We build C3 term by term: the i pointer marks the left factor and the k-1-i pointer marks its symmetric partner. The first and last terms mirror each other (C0*C2 and C2*C0), and the middle term C1*C1 is where the two pointers meet. The three products 2 + 1 + 2 sum to 5, so C3 = 5. Then C4 fills the same way to 14.

Pseudocode

dp = array of zeros, length n + 1
dp[0] = 1
for k from 1 to n:
    total = 0
    for i from 0 to k - 1:
        total += dp[i] * dp[k - 1 - i]   # symmetric pair
    dp[k] = total
return dp[n]

The Python solution

def catalan(n):
    dp = [0] * (n + 1)
    dp[0] = 1
    for k in range(1, n + 1):
        total = 0
        for i in range(k):
            total += dp[i] * dp[k - 1 - i]
        dp[k] = total
    return dp[n]

• dp is the table; dp[k] ends up holding the kth Catalan number.
• dp[0] = 1 is the only base case the recurrence needs.
• The outer loop fills dp[1], dp[2], … in order, so every value an inner term reads is already computed.
• Line 7 is the heart of it: dp[i] * dp[k - 1 - i] multiplies a left factor by its symmetric partner, and range(k) sweeps the split point across all positions.
• After the inner loop, total is the full sum — store it as dp[k] and move on.

Complexity

The inner loop does up to k multiplications for each k, so the total work is 1 + 2 + … + n, which is O(n²). We store one value per index, giving O(n) space. (There is also a closed form Cn = (2n)! / ((n+1)! * n!), but the DP is the version interviewers want to see derived.)

When this pattern shows up

Practice