Generate Pascal's Triangle in Java
Problem
Pascal's triangle is a triangular array of binomial coefficients, where each row is built from the row above it by adding adjacent pairs, and every row starts and ends with 1.
Given a number of rows, generate that many rows of Pascal's triangle.
Java Program
public class PascalsTriangle {
public static void main(String[] args) {
int rows = 5;
int[][] triangle = new int[rows][];
for (int i = 0; i < rows; i++) {
triangle[i] = new int[i + 1];
triangle[i][0] = 1;
triangle[i][i] = 1;
for (int j = 1; j < i; j++) {
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j]; // sum of the two entries above
}
}
for (int[] row : triangle) {
StringBuilder line = new StringBuilder();
for (int value : row) {
if (line.length() > 0) line.append(" ");
line.append(value);
}
System.out.println(line);
}
}
}Output
Core Logic
Building each row from the row directly above it, one entry at a time, reconstructs the whole triangle without needing any combinatorial formula.
- 1Each row
iis sized to holdi + 1entries, and its first and last entries are always set to1. - 2Every entry in between is the sum of the two entries above it:
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j]. - 3This mirrors how Pascal's triangle is usually drawn by hand — each number is the sum of the two numbers diagonally above it.
- 4Once the full 2D array is filled, each row is joined into a space-separated line and printed.
1 3 3 1) comes directly from row 3 (1 2 1): the middle entries 3 and 3 are each the sum of an adjacent pair from the row above.Key Point: Every entry in the triangle is technically a binomial coefficient — row i, position j equals C(i, j) — but building it additively from the row above avoids computing any factorials at all.
Why: Each row holds as many entries as its row number, so both the total work to fill every cell and the memory to store the whole triangle grow proportionally to rows².
Key Concepts
Approach 2: Java 8
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class PascalsTriangleStream {
static long binomial(int n, int k) {
long result = 1;
for (int i = 0; i < k; i++) {
result = result * (n - i) / (i + 1); // multiply and divide in the same step to stay an integer
}
return result;
}
public static void main(String[] args) {
int rows = 5;
// For each row i, computes C(i, j) for every position j in that row
IntStream.range(0, rows)
.mapToObj(i -> IntStream.rangeClosed(0, i)
.mapToObj(j -> String.valueOf(binomial(i, j)))
.collect(Collectors.joining(" ")))
.forEach(System.out::println);
}
}
Output
Core Logic
Since every entry is really just a binomial coefficient, each row can be computed independently with a formula instead of depending on the row before it — a shape that fits streams naturally.
- 1
binomial(n, k)computesC(n, k)directly with a small multiplicative loop, the same technique used elsewhere to compute combinations. - 2The outer
IntStream.range(0, rows)generates one stream element per row indexi. - 3For each row, an inner
IntStream.rangeClosed(0, i)computesC(i, j)for every positionjin that row, joining the values with spaces. - 4
forEach(System.out::println)prints each completed row as it's produced.
4, the inner stream computes C(4,0), C(4,1), C(4,2), C(4,3), C(4,4) — 1, 4, 6, 4, 1 — the same row the additive version builds.Key Point: Because each row is now computed independently, only one row needs to exist in memory at a time — unlike the additive version, which keeps the entire triangle around so later rows can reference earlier ones.
Why: Each row is computed independently via the direct binomial formula, so only one row needs to be held in memory at a time instead of the full triangle.