Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
The nth Catalan number Cₙ counts a surprising number of things: distinct BSTs with n nodes, valid sequences of n balanced parenthesis pairs, full binary trees with n+1 leaves, and triangulations of a polygon. Two ways to compute it. DP: C₀ = 1 and Cₙ = Σ (Cᵢ · Cₙ₋₁₋ᵢ) for i = 0..n−1, in O(n²) — the split recurrence that mirrors choosing a root. Closed form: Cₙ = C(2n, n) / (n + 1), in O(n) — one central binomial coefficient divided by n+1. Under a prime modulus, the division becomes multiply-by-modular-inverse.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise the Catalan structure behind 'count the BSTs / balanced parens', can write the split-point convolution recurrence with the correct n−1 indexing, and know the closed form plus how to handle its division under a modulus.
Where candidates slip
Indexing the split as Cᵢ·Cₙ₋ᵢ (sums to n, off by one) instead of Cᵢ·Cₙ₋₁₋ᵢ, or integer-dividing C(2n,n) by (n+1) under a prime mod instead of multiplying by the inverse.
How to stand out
Explain WHY the recurrence is a convolution — fixing the root (or the first matched pair) splits the remaining n−1 items into independent left/right sub-instances — and mention the closed form turns O(n²) into O(n).
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Fixing the root splits the remaining n−1 nodes into an i-node left subtree and an (n−1−i)-node right subtree — independent, so the counts multiply and sum over i.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Convolution DP (Baseline / All Values)
1Hint 1Explore hintHide hint
Think about counting BSTs with n nodes. If you fix which value is the root, what are the left and right subtrees, and are they independent?
2Hint 2Explore hintHide hint
Root choice i splits the rest into a left subtree of i nodes and a right subtree of n−1−i nodes. Both are smaller Catalan counts, and they're chosen independently — so their counts multiply.
3Hint 3Explore hintHide hint
Sum that product over every root choice: C[n] = Σ C[i]·C[n−1−i] for i = 0..n−1, with C[0] = 1. Build the table from small n upward.
A · Core idea
Build the Catalan values bottom-up from the split recurrence. Set C[0] = 1, then for each n compute C[n] = Σ_{i=0}^{n−1} C[i]·C[n−1−i].
Where the recurrence comes from. Count BSTs with n nodes (values 1..n). Fix the root to be the (i+1)-th smallest value. Then the i values below it form the left subtree and the n−1−i values above it form the right subtree. Crucially, the shape of the left subtree and the shape of the right subtree are chosen independently, and each is itself a Catalan count on fewer nodes — C[i] and C[n−1−i]. Independence means the number of combined trees for this root is the product C[i]·C[n−1−i]. Summing over all n root choices gives the recurrence. The identical split explains balanced parentheses (fix the partner of the first (: it encloses i pairs, leaving n−1−i pairs after it) and polygon triangulations.
Why the indices sum to n−1, not n. Fixing the root consumes one node, so only n−1 remain to distribute between the two subtrees. That's why the second index is n−1−i. Writing C[i]·C[n−i] (summing to n) double-counts and is the single most common bug here.
Why bottom-up. Each C[n] depends only on smaller indices, so filling the table in increasing n means every term on the right is already known. No recursion stack, no recomputation.
Cost and overflow. Computing C[n] does n multiplications, so the whole table is O(n²). Catalan values explode like 4ⁿ, so for exact values beyond n ≈ 33 you must work modulo a prime (reduce after each multiply, long in Java) or use big integers in Python.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4Array state
C[0]
base case = 1
14C · Code with teaching comments
Reference implementation previewpublic long catalan(int n) { long[] c = new long[n + 1]; c[0] = 1; for (int k = 1; k <= n; k++) { long sum = 0;Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The DP is the honest expression of the structure: 'fix one element, multiply the independent sub-counts, sum over choices.' It's the right tool when you need every C₀..Cₙ (e.g. as a subroutine). Its only weakness is the O(n²) convolution — which the closed form removes when you need just one value.
ComplexityO(n²) time, O(n) space — Computing C[n] sums n products, and we do this for each n up to the target, giving 1 + 2 + … + n ≈ n²/2 = O(n²) multiplications. The table of Catalan values is O(n) space.
E · Edge cases and pitfalls4Indices summing to k instead of k−1 — the off-by-one that breaks the count.Explore edge casesHide edge cases
Pitfalls
- Indices summing to k instead of k−1 — the off-by-one that breaks the count.
- Forgetting C[0] = 1 — zeroes the entire table.
- Letting the exact value overflow for n > 33 — switch to mod p or big integers.
- Recomputing recursively without memoisation — exponential blowup.
Approach 2 of 2 · Optimal
Closed Form C(2n,n)/(n+1) (Optimal Single Value)
1Hint 1Explore hintHide hint
There's a closed form: Cₙ = C(2n, n) / (n + 1). It divides exactly over the integers. How do you compute a single C(2n, n) efficiently?
2Hint 2Explore hintHide hint
Precompute factorials and their modular inverses up to 2n, then C(2n, n) = fact[2n]·invFact[n]·invFact[n] mod p.
3Hint 3Explore hintHide hint
The /(n+1) is a division — under a prime mod, multiply by the modular inverse of (n+1) via Fermat: (n+1)^(p−2) mod p. Never integer-divide modulo p.
A · Core idea
Use the identity Cₙ = C(2n, n) / (n + 1), where C(2n, n) is the central binomial coefficient.
Why the formula holds (sketch). C(2n, n) counts all lattice paths from (0,0) to (n,n) using unit right/up steps. The Catalan number counts only those that never cross above the diagonal. André's reflection argument shows the 'bad' paths are in bijection with C(2n, n+1) of them, and C(2n,n) − C(2n,n+1) = C(2n,n)/(n+1). The upshot: the central binomial, divided by n+1, is exactly Cₙ — and the division is always exact over the integers.
Computing it exactly for small n. Multiply C(2n, n) with a running product (dividing as you go to keep numbers small) and divide once by n+1. Fine while Cₙ fits in 64 bits (n ≤ 33).
Computing it modulo a prime for large n. Two changes. First, C(2n, n) = fact[2n] · invFact[n] · invFact[n] mod p, using precomputed factorials and Fermat inverse-factorials (one modpow plus a backward sweep, exactly as in nCr mod p). Second — the trap — the /(n+1) cannot be integer division under a modulus. Replace it with multiplication by the modular inverse of n+1: since p is prime and p > n+1, (n+1)⁻¹ ≡ (n+1)^(p−2) (mod p) by Fermat. So Cₙ ≡ C(2n,n) · (n+1)^(p−2) (mod p).
Why p > 2n matters. The factorial fact[2n] must not contain a factor of p, or it would be 0 mod p and have no inverse. Requiring p > 2n guarantees that and keeps every inverse well-defined.
Overflow safety. All modular products are of two values below p ≈ 10⁹, so each fits in a 64-bit long provided you reduce mod p after every multiplication. Python integers are unbounded; the modulus there is for matching the math and for speed.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, exactArray state
n=0..4
C(2n,n): 1, 2, 6, 20, 70
14C · Code with teaching comments
D · Why it works and complexityO(n) precompute, O(1) per value timeO(n) for factorial tables (O(1) for exact small n) spaceOpen the invariant and proofExplore the proofHide the proof
The closed form trades the O(n²) convolution for O(n) factorial precompute and O(1) per value — the right move when you need a single large Cₙ. The two things to get right: it's C(2n,n) over (n+1), and under a modulus that division is a multiply-by-inverse. It reuses the exact factorial/inverse machinery from nCr mod p, so Catalan is essentially a one-line wrapper around binomial coefficients.
ComplexityO(n) precompute, O(1) per value time, O(n) for factorial tables (O(1) for exact small n) space — Building factorial and inverse-factorial tables up to 2n is O(n) (one Fermat inverse plus a backward sweep). After that, each Catalan number is a constant number of multiplications, so O(1) per value. Tables are O(n) space.
E · Edge cases and pitfalls7n = 0 — C(0,0)/1 = 1; the loop runs zero times and result/1 = 1.Explore edge casesHide edge cases
Edge cases handled
n = 0C(0,0)/1 = 1; the loop runs zero times and result/1 = 1.n = 1C(2,1)/2 = 2/2 = 1.large n mod pUses factorial tables and Fermat inverse of n+1; needs p prime and p > 2n.
Pitfalls
- Integer-dividing C(2n,n) by (n+1) under a modulus — must multiply by the inverse.
- Using fact[2n] when p ≤ 2n — fact[2n] is 0 mod p and has no inverse; require p > 2n.
- Multiplying out C(2n,n) without divide-as-you-go in the exact path — overflows sooner.
- Forgetting that the exact path only survives to n ≈ 33 before 64-bit overflow.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code preview// Exact for small n (Cn fits in 64 bits, n <= 33). public long catalanClosed(int n) { long result = 1; // C(2n, n) computed with divide-as-you-go to stay small. for (int i = 0; i < n; i++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Off-by-one in the split recurrence
Fixing the root uses one node, leaving n−1 to split. The product must be Cᵢ·Cₙ₋₁₋ᵢ (indices sum to n−1). Using Cᵢ·Cₙ₋ᵢ over-counts and gives wrong values from C₂ onward.
Explore the code comparisonHide the code comparison
Off-by-one in the split recurrence
Fixing the root uses one node, leaving n−1 to split. The product must be Cᵢ·Cₙ₋₁₋ᵢ (indices sum to n−1). Using Cᵢ·Cₙ₋ᵢ over-counts and gives wrong values from C₂ onward.
Don't write this
for (int i = 0; i < k; i++) {
sum += c[i] * c[k - i]; // indices sum to k — WRONG
}Write this instead
for (int i = 0; i < k; i++) {
sum += c[i] * c[k - 1 - i]; // indices sum to k-1
}2Dividing by (n+1) under a modulus
Modular arithmetic has no division. C(2n,n)/(n+1) mod p must become C(2n,n)·(n+1)⁻¹ mod p, with the inverse from Fermat. Integer division gives a wrong residue.
Explore the code comparisonHide the code comparison
Dividing by (n+1) under a modulus
Modular arithmetic has no division. C(2n,n)/(n+1) mod p must become C(2n,n)·(n+1)⁻¹ mod p, with the inverse from Fermat. Integer division gives a wrong residue.
Don't write this
central = fact[2 * n] * inv_fact[n] % p * inv_fact[n] % p
return central // (n + 1) % p # WRONG under a modulusWrite this instead
central = fact[2 * n] * inv_fact[n] % p * inv_fact[n] % p
return central * pow(n + 1, p - 2, p) % p # multiply by inverse3Exact value overflow for large n
Catalan numbers grow like 4ⁿ; C₃₅ exceeds a signed 64-bit integer. Computing exactly with long silently overflows to garbage.
Explore the code comparisonHide the code comparison
Exact value overflow for large n
Catalan numbers grow like 4ⁿ; C₃₅ exceeds a signed 64-bit integer. Computing exactly with long silently overflows to garbage.
Don't write this
long c = catalanClosed(40); // overflows long — wrongWrite this instead
long c = catalanMod(40, 1_000_000_007L, fact, invFact); // work mod pRevise
Carry the pattern into the interview
Pattern to remember
Catalan = split-point DP recurrence, or central binomial C(2n,n)/(n+1)
Code pattern to memorize
DP: C[0] = 1; C[n] = sum over i in [0, n-1] of C[i] * C[n-1-i]
Closed form: C(n) = C(2n, n) / (n + 1)
Mod p (prime): C(n) = C(2n, n) * inverse(n + 1) mod pRules to remember
- 1The DP recurrence splits on the root / first matched pair:
Cₙ = Σ Cᵢ · Cₙ₋₁₋ᵢ. The two indices must sum ton − 1(the remaining items after fixing one), notn— the off-by-one trap. - 2Closed form
C(2n,n)/(n+1)divides exactly over the integers, but under a prime mod you must multiply by the modular inverse ofn+1, never integer-divide. - 3Catalan numbers grow like
4ⁿ / (n^1.5 √π)—C₃₅already overflows a 64-bit integer, so uselongcarefully or compute mod p / with big integers. - 4DP is
O(n²); the closed form isO(n). Prefer the formula when you only need a singleCₙ, the DP when you also want all ofC₀..Cₙ. - 5Base case
C₀ = 1(the empty structure: one empty tree, one empty parenthesis string) — forgetting it zeroes the whole table.
Use this pattern when
- Counting **distinct BSTs / full binary trees** with n nodes (LeetCode 96)
- Counting **valid balanced-parenthesis** sequences of n pairs (LeetCode 22 counts them)
- Counting polygon triangulations, monotonic lattice paths under the diagonal, or stack-sortable permutations
- Any recurrence of the shape 'pick a split point, multiply the two independent sub-counts, sum over splits'
Choose another pattern when
- You must **enumerate** the structures, not count them → backtracking, not a Catalan formula
- The objects aren't independent across the split → the product form Cᵢ·Cₙ₋₁₋ᵢ doesn't apply
- n is tiny and one-off → just look up or hardcode the small Catalan values
- You need it mod a **composite** → Fermat's inverse of n+1 fails; use extended-GCD inverse
Interview takeaway
Catalan numbers are the answer whenever a count decomposes as 'fix one element, then the left and right parts are independent and each is a smaller instance of the same count'. That split gives the O(n²) convolution DP; the closed form C(2n,n)/(n+1) collapses it to O(n). The recurring traps are the n−1 index in the split and treating the closed-form division as integer division under a modulus.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCatalan / convolution counting. Recognise it whenever a count decomposes as 'fix one element, the left and right parts are independent smaller instances'. The O(n²) split DP gives all values; the O(n) closed form C(2n,n)/(n+1) gives one. Shows up in BST counts, balanced parentheses, triangulations, and stack-sortable permutations.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Unique Binary Search TreesComing soonThe count of BSTs with n nodes IS Cₙ — the convolution DP is the intended solution.
- Generate ParenthesesComing soonThe number of valid n-pair strings is Cₙ; generating them is backtracking, counting them is Catalan.
- nCr mod pThe closed form is just a central binomial coefficient over n+1 — reuses factorial/inverse tables.
- Lucas' TheoremIf you need Catalan mod a small prime with large n, compute C(2n,n) mod p via Lucas.