Description
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.
Constraints
Approach
Links
Examples
Input: 5
Output:
[
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1]
]
Solutions
/**
* 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;
}
}
Follow up
