In Pascal's triangle, each number is the sum of the two numbers directly above it.
Last updated
/**
* Time complexity : O(N*N)
* Space complexity : O(N*N)
*/
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList();
if(numRows >= 1) {
triangle.add(List.of(1));
}
for(int i = 1; i < numRows; i++) {
List<Integer> prevRow = triangle.get(i-1);
List<Integer> currRow = new ArrayList();
currRow.add(1);
for(int j = 0; j < prevRow.size()-1; j++) {
currRow.add(prevRow.get(j) + prevRow.get(j+1));
}
currRow.add(1);
triangle.add(currRow);
}
return triangle;
}
}/**
* Time complexity : O(N*N)
* Space complexity : O(N*N)
*/
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> pascals = new ArrayList();
if(numRows == 0) return pascals;
List<Integer> row = null, prevRow = null;
for(int i = 0; i < numRows; i++) {
row = new ArrayList();
for(int j = 0; j <= i; j++) {
if(j == 0 || j == i) {
row.add(1);
} else {
row.add(prevRow.get(j-1)+prevRow.get(j));
}
}
prevRow = row;
pascals.add(row);
}
return pascals;
}
}