Problem
Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
Solution
The current row can be calculated from the previous row. The solution is straight forward, but we need to write code carefully so that it covers all the corner cases.
The time cost is proportional to the total number of elements in all the arrays, which is O(n^2). No extra space is needed, the space cost is O(1).
public class PascalsTriangle {
public static void pascalsTriangle(int n) { //5
int[][] triangle = new int[n][];
for(int i = 0; i < n; i++) {//2
if(i == 0) {
triangle[0] = new int[]{1};
} else {
int[] pre = triangle[i - 1];//{1,1}
int[] cur = new int[i+1];//{1, 2, 1}
cur[0] = pre[0];
for(int j = 1; j < i; j++) {
cur[j] = pre[j-1] + pre[j];
}
cur[i] = pre[pre.length - 1];
triangle[i] = cur;
}
}
System.out.println("[");
for(int i = 0; i < n; i++) {//0
for(int j = 0; j < n - i; j++)
System.out.print(" ");
System.out.print("[");
for(int j = 0; j < triangle[i].length - 1; j++) {
System.out.print(triangle[i][j] + ", ");
}
System.out.print(triangle[i][triangle[i].length - 1] + "]");
System.out.println();
}
System.out.println("]");
}
public static void main(String...args) {
pascalsTriangle(5);
}
}
public static void pascalsTriangle(int n) { //5
int[][] triangle = new int[n][];
for(int i = 0; i < n; i++) {//2
if(i == 0) {
triangle[0] = new int[]{1};
} else {
int[] pre = triangle[i - 1];//{1,1}
int[] cur = new int[i+1];//{1, 2, 1}
cur[0] = pre[0];
for(int j = 1; j < i; j++) {
cur[j] = pre[j-1] + pre[j];
}
cur[i] = pre[pre.length - 1];
triangle[i] = cur;
}
}
System.out.println("[");
for(int i = 0; i < n; i++) {//0
for(int j = 0; j < n - i; j++)
System.out.print(" ");
System.out.print("[");
for(int j = 0; j < triangle[i].length - 1; j++) {
System.out.print(triangle[i][j] + ", ");
}
System.out.print(triangle[i][triangle[i].length - 1] + "]");
System.out.println();
}
System.out.println("]");
}
public static void main(String...args) {
pascalsTriangle(5);
}
}
Time complexity O(n^2), space complexity O(1).
