Program for nth Catalan Number

The problem, simply

Find the nth Catalan number C(n). The numbers go 1, 1, 2, 5, 14, 42, 132, ... for n = 0, 1, 2, 3, 4, 5, 6.

The easiest way to picture them: C(n) is how many different binary search trees you can build with the keys 1 to n. The rule that builds them is C(0) = 1 and C(n) = C(0) x C(n-1) + C(1) x C(n-2) + ... + C(n-1) x C(0).

A story to remember it

Picture it

Examples

Way 1: the simple way

Code the rule as it is written.

1. If n <= 1, return 1.
2. For each top i from 0 to n - 1, add C(i) x C(n - 1 - i).

class Solution {
    public long catalan(int n) {
        if (n <= 1) return 1;
        long total = 0;
        for (int i = 0; i < n; i++) {
            total += catalan(i) * catalan(n - 1 - i);   // left family x right family
        }
        return total;
    }
}

How long it takes: each call makes calls for every smaller size, twice. The count of calls grows like O(3^n). Extra room: the call chain, O(n).

Way 2: the clever way

Fill a row C[0..n] from left to right. When you reach box i, every smaller box is already filled.

1. C[0] = 1, C[1] = 1.
2. For i = 2 to n: C[i] = sum of C[j] x C[i - 1 - j] for j = 0 to i - 1. Here j nodes go left and i - 1 - j go right.
3. Return C[n].

class Solution {
    public long catalan(int n) {
        long[] C = new long[n + 2];
        C[0] = 1;
        C[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                C[i] += C[j] * C[i - 1 - j];   // j on the left, i-1-j on the right
            }
        }
        return C[n];
    }
}

How long it takes: box i costs i steps, so O(n^2) in all. Extra room: the row, O(n).

Another way: one loop with the formula

There is a shortcut formula: C(n) = C(2n, n) / (n + 1). It gives a neat step from one Catalan number to the next: C(i) = C(i - 1) x 2(2i - 1) / (i + 1). Multiply first, then divide, and the division is always exact.

class Solution {
    public long catalan(int n) {
        long c = 1;                              // C(0)
        for (int i = 1; i <= n; i++) {
            c = c * 2 * (2 * i - 1) / (i + 1);   // exact division
        }
        return c;
    }
}

This is O(n) time and O(1) room. The product before the division overflows a little earlier than the answer does (around n = 33), so use BigInteger or modular inverses for big n.

Watch out for

• The top node itself is not in either family. That is why the sizes add up to n - 1, not n.
• C[1] must exist even when n = 0. Size the row n + 2, or handle n = 0 first.
• The numbers overflow long after C(35). With a modulo, you cannot use the division formula directly. Use the O(n^2) row, or modular inverses.

What interviewers ask next

• Where else does C(n) show up? Valid bracket strings with n pairs, ways to cut a polygon with n + 2 corners into triangles, mountain ranges with n up steps and n down steps, and paths in an n by n grid that never cross the diagonal.
• Unique BSTs (LeetCode 96) is exactly C(n). Unique BSTs II asks to build all the trees: recursion over the top, combining every left tree with every right tree.
• Count full binary trees with n leaves. That is C(n - 1).
• How fast does it grow? About 4^n / (n^1.5 x sqrt(pi)).

Remember this

Grown-up words: the families are subtrees, the shapes are binary search trees, the rule is the Catalan recurrence, the filled row is 1D dynamic programming, and the shortcut uses the binomial coefficient.