Pascal's Triangle solution using TypeScript
This post outlines my TypeScript solution to the "Pascal's Triangle" question on LeetCode.
Time Complexity: Because this solution will iterate n(n+1)/2 times, the time complexity is O(n^2).
Space Complexity: Because this solution will create n(n+1)/2 elements, the space complexity is O(n^2).
/**
* Pascal's Triangle
* Given a non-negative integer numRows,
* generate the first numRows of Pascal's triangle.
*
* Time Complexity: O(n*n)
* Space Complexity: O(n*n)
*
* generate(3) // [[1],[1,1],[1,2,1]]
* generate(4) // [[1],[1,1],[1,2,1],[1,3,3,1]]
*/
function generate(numRows: number): number[][] {
let triangle: number[][] = [];
let y = 0;
while (y < numRows) {
// row 1
if (y === 0) {
triangle.push([1]);
}
// row 2
else if (y === 1) {
triangle.push([1, 1]);
}
// row n+1
else {
let x = 0;
let row = [1];
while (x < y - 1) {
row.push(triangle[y-1][x]
+ triangle[y-1][x+1]);
x += 1;
}
row.push(1);
triangle.push(row);
}
y += 1;
}
return triangle;
}