118. Pascal's Triangle

• python3

📎 Problem

Given an integer numRows, return the first numRows of Pascal's triangle.

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

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

• 1 <= numRows <= 30

Pseudocode

1. Create the result array and initialize it for the case when the number of rows is one.
2. If the number of rows is greater than one, set the first and last elements of each row to one.
3. Calculate the values starting from the third row.
4. Return the result array.

Code

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        
        result = [[1]]

        for i in range(1, numRows):
            row = [0] * (i+1)
            row[0] = 1
            row[i] = 1
            for j in range(1, i):
                row[j] = result[i-1][j-1]+result[i-1][j]
            result.append(row)
        
        return result

Result

• Time Complexity : O(n^2)
• Space Complexity : O(n^2)