Pascal’s Triangle
Given an integer numRows, return the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Example 2:
Input: numRows = 1
Output: [[1]]
Constraints:
1 <= numRows <= 30
My Solution
The corner case is if numRows, is 1, in which we just initialize a list with 1 and return. For all other values of numRows, we loop through each row, add a 1 to the list at the beginning, then for every two adjacent values of the previous list, we add the sum, and finally we add a 1 at the end and add the row to the pascal list.
Time complexity would be O(n²) because there are n rows and for each row we iterate through the previous row, which has O(n) elements. Space complexity would also be O(n²) to store the lists.
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> pascal = new ArrayList<>();
List<Integer> row1 = new ArrayList<>();
row1.add(1);
pascal.add(row1);
if (numRows == 1) {
return pascal;
}
for (int i = 1; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
List<Integer> prev = pascal.get(i-1);
row.add(1);
int n = prev.size();
for (int j = 0; j < n-1; j++) {
row.add(prev.get(j) + prev.get(j+1));
}
row.add(1);
pascal.add(row);
}
return pascal;
}
}