This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given *numRows*, generate the first *numRows* of Pascal's triangle.

For example, given *numRows* = 5,

Return

[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

b'

\n\n#### Approach #1 Dynamic Programming [Accepted]

\n

\n

'
**Intuition**

If we have the a row of Pascal\'s triangle, we can easily compute the next\nrow by each pair of adjacent values.

\n**Algorithm**

Although the algorithm is very simple, the iterative approach to constructing\nPascal\'s triangle can be classified as dynamic programming because we\nconstruct each row based on the previous row.

\nFirst, we generate the overall `triangle`

list, which will store each row as\na sublist. Then, we check for the special case of , as we would otherwise\nreturn . If , then we initialize `triangle`

with \nas its first row, and proceed to fill the rows as follows:

!?!../Documents/118_Pascals_Triangle.json:1280,720!?!

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : \n

\nAlthough updating each value of

\n`triangle`

happens in constant time, it\nis performed times. To see why, consider how many\noverall loop iterations there are. The outer loop obviously runs\n times, but for each iteration of the outer loop, the inner\nloop runs times. Therefore, the overall number of`triangle`

updates\nthat occur is , which, according to Gauss\' formula,\nis\n\n

\n \n - \n
Space complexity : \n

\nBecause we need to store each number that we update in

\n`triangle`

, the\nspace requirement is the same as the time complexity. \n

\n

Analysis and solutions written by: @emptyset

\n