Print Pascal's Triangle as a Pattern
Solve this ProblemEasy15 min
Topics
BasicsPatternsMath
Companies
TCSInfosysWipro
Given
n, return the first n rows of Pascal's triangle as centred text: row i (counting from 0) has n − 1 − i leading spaces, followed by its values separated by single spaces.
Every edge value is 1 and every inner value is the sum of the two values above it. Those values are the binomial coefficientsBinomial CoefficientC(i, j): the number of ways to choose j items from i. Row i of Pascal's triangle lists C(i, 0) to C(i, i)., which also lets each value be computed from its left neighbour. The single space between numbers is what produces the triangle shape when the rows are printed.
Test Case 1:
Input:n = 4
Output:[" 1", " 1 1", " 1 2 1", "1 3 3 1"]
Explanation:Each row is centred with leading spaces; inside a row, the values are separated by single spaces.
Test Case 2:
Input:n = 1
Output:["1"]
Explanation:Just the 1 at the apex.
Constraints
- ◆
1 ≤ n ≤ 10
Try the Dry Run
Approach & Solutions
Add the Two Numbers AboveGood
Build the triangle row by row, keeping only the previous row. Each new row starts and ends with 1, and every inner value is the sum of the two values diagonally above it: prev[j − 1] + prev[j]. Then write the row as text: n − 1 − i spaces, then the values separated by single spaces.
Time
O(n²)Space
O(n) extraJava
class Solution {
public String[] printPascalsTriangle(int n) {
String[] result = new String[n];
int[] prev = new int[0];
for (int i = 0; i < n; i++) {
int[] cur = new int[i + 1];
cur[0] = 1;
cur[i] = 1;
for (int j = 1; j < i; j++) {
cur[j] = prev[j - 1] + prev[j];
}
StringBuilder row = new StringBuilder(" ".repeat(n - 1 - i));
for (int j = 0; j <= i; j++) {
row.append(j == 0 ? "" : " ").append(cur[j]);
}
result[i] = row.toString();
prev = cur;
}
return result;
}
}Running Binomial CoefficientOptimal
The j-th value in row i is the binomial coefficient C(i, j), and consecutive values are linked: C(i, j + 1) = C(i, j) × (i − j) / (j + 1). Start each row at 1 and step along it with that formula — no previous row needs to be stored. The division is always exact.
Time
O(n²)Space
O(1) extraJava
class Solution {
public String[] printPascalsTriangle(int n) {
String[] result = new String[n];
for (int i = 0; i < n; i++) {
StringBuilder row = new StringBuilder(" ".repeat(n - 1 - i));
int value = 1;
for (int j = 0; j <= i; j++) {
row.append(j == 0 ? "" : " ").append(value);
value = value * (i - j) / (j + 1);
}
result[i] = row.toString();
}
return result;
}
}