118_Pascal's Triangle

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input:
 5

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

Solution:

Idea:

• Initiate the structure of Pascal's triangle in a 2D array, and loop over each entry except the beginning and end of each row.

Time complexity: $O(n^2)$, where n is numRows

Space complexity: $O(n^2)$, where n is numRows

def generate_pascal_triangle(numRows):
    """
    :type numRows: int
    :rtype: List[List[int]]
    """
    output = [[1]*(i+1) for i in range(numRows)]
    for i in range(2, numRows) :
        for j in range(1, i) :
            output[i][j] = output[i-1][j-1] + output[i-1][j]
    return output