Find Nth Catalan Number in Java
Problem
The Nth Catalan number counts things like the number of ways to arrange balanced parentheses or the number of distinct binary search trees with n nodes, and can be built up from smaller Catalan numbers.
Given a number n, find the Nth Catalan number.
Java Program
public class NthCatalanNumber {
public static void main(String[] args) {
int n = 4;
long[] catalan = new long[n + 1];
catalan[0] = 1; // base case of the sequence
for (int i = 1; i <= n; i++) {
long sum = 0;
for (int j = 0; j < i; j++) {
sum += catalan[j] * catalan[i - 1 - j]; // pairs of already-known smaller Catalan numbers
}
catalan[i] = sum;
}
System.out.println("Catalan number at n = " + n + ": " + catalan[n]);
}
}Output
Core Logic
Building every Catalan number from 0 up to n, using the recurrence that defines each one in terms of all the smaller ones, avoids recomputing the same smaller values over and over.
- 1
catalan[0]is set to1, the base case of the sequence. - 2Each subsequent
catalan[i]is built from every pair of already-known smaller Catalan numbers:catalan[j] * catalan[i - 1 - j], summed over everyjfrom0toi - 1. - 3This mirrors the mathematical recurrence
C(i) = Σ C(j) × C(i-1-j), which is exactly how the Catalan sequence is defined. - 4By the time the outer loop reaches
i = n, every smaller Catalan number it depends on has already been computed and stored.
n = 4, the sequence builds up as 1, 1, 2, 5, 14 — each new value computed entirely from the ones before it.Key Point: This is the same idea as memoized Fibonacci — instead of recomputing smaller Catalan numbers from scratch every time they're needed, each one is calculated once and reused.
Why: Building each Catalan number requires summing over all smaller pairs, so the nested loops do O(n²) work while the array holds n + 1 running values.
Key Concepts
Approach 2: Binomial Coefficient Formula
public class NthCatalanNumberFormula {
public static void main(String[] args) {
int n = 4;
long binomial = 1;
// Builds C(2n, n) iteratively using the multiplicative formula for binomial coefficients
for (int i = 0; i < n; i++) {
binomial = binomial * (2L * n - i) / (i + 1);
}
long catalan = binomial / (n + 1);
System.out.println("Catalan number at n = " + n + ": " + catalan);
}
}
Output
Core Logic
The Nth Catalan number also has a direct closed-form formula — C(2n, n) divided by (n + 1) — which sidesteps the recurrence entirely.
- 1
binomialbuilds upC(2n, n)using the same multiplicative formula the combination program uses, one factor at a time. - 2Multiplying before dividing at each step keeps every intermediate value an exact integer, avoiding the need for factorials of very large numbers.
- 3Once
C(2n, n)is known, dividing it byn + 1gives the Catalan number directly. - 4No array or recurrence is needed — the whole computation is a single loop of
nmultiplications and divisions.
n = 4, the loop builds C(8, 4) = 70, and 70 / (4 + 1) = 14 — the same answer the DP table found.Key Point: This trades the DP table's O(n) space for O(1) space, at the cost of needing to know (or derive) the binomial-coefficient identity in the first place.
Why: The binomial coefficient is built up with a single loop of n multiplications and divisions, and only one running value is kept.
Key Concepts
Approach 3: Java 8
import java.util.stream.IntStream;
public class NthCatalanNumberStream {
public static void main(String[] args) {
int n = 4;
// Folds the binomial coefficient formula across each index, just like the loop version
long binomial = IntStream.range(0, n)
.mapToObj(i -> i)
.reduce(1L, (acc, i) -> acc * (2L * n - i) / (i + 1), (a, b) -> a * b);
long catalan = binomial / (n + 1);
System.out.println("Catalan number at n = " + n + ": " + catalan);
}
}
Output
Core Logic
The binomial-coefficient loop is a running product-and-divide carried from one iteration to the next — exactly the shape a stream fold expresses with reduce().
- 1
IntStream.range(0, n).mapToObj(i -> i)turns the loop's index range into aStream<Integer>, sinceIntStreamitself has no three-argumentreduce(). - 2
.reduce(1L, (acc, i) -> acc * (2L * n - i) / (i + 1), (a, b) -> a * b)folds the running binomial value across every index, the same multiply-then-divide each iteration performed. - 3The identity
1Land the accumulator lambda reproduce the loop's starting value and per-step update exactly; the combiner is required by thisreduce()overload but never actually runs, since the stream here is sequential. - 4Dividing the folded result by
n + 1afterward gives the Catalan number, same as the loop-based version.
n = 4, folding across indices 0, 1, 2, 3 builds the binomial coefficient up to 70, and 70 / 5 = 14.Key Point: reduce() is the stream vocabulary for exactly this pattern — 'combine a running value with each element' — which is what the imperative loop was already doing one line at a time.
Why: The fold still performs one multiplication and division per index from 0 to n, carrying only a single running value forward.