118. Pascal's Triangle


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]
]


Approach #1 Dynamic Programming [Accepted]

Intuition

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

Algorithm

Although the algorithm is very simple, 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 , as we would otherwise return . If , then we initialize triangle with as its first row, and proceed to fill the rows as follows:

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

Complexity Analysis

  • Time complexity :

    Although updating each value of triangle happens in constant time, it is performed times. To see why, consider how many overall loop iterations there are. The outer loop obviously runs times, but for each iteration of the outer loop, the inner loop runs times. Therefore, the overall number of triangle updates that occur is , which, according to Gauss' formula, is

  • Space complexity :

    Because we need to store each number that we update in triangle, the space requirement is the same as the time complexity.

Analysis and solutions written by: @emptyset

Submit Solution