Problem statement:
Given an integer numRows, return the first numRows of Pascal’s triangle.
Input Format:
Number of Rows in Pascal Triangle
Output Format:
List containing arrays representing rows of Pascal Triangle
Sample Input:
5
Sample Output:
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Approach:
the iterative approach to constructing Pascal’s triangle can be classified as dynamic programming because we construct each row based on the previous row.
First, we generate the overall triangle
list, which will store each row as a sublist. Then, we check for the special case of 00, as we would otherwise return [1][1]. Since numRowsnumRows is always greater than 00, we can initialize triangle
with [1][1] as its first row, and proceed to fill the rows as follows:
Time complexity: O(NumRows²)
Space complexity: O(1)
Code:
Thanks for Reading
Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.
Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.