Solution 1 - Iterative Row Building

Given an integer numRows, return the first numRows rows of Pascal's triangle. Each row starts and ends with 1, and every other element is the sum of the two elements directly above it from the previous row. Build the triangle row by row, computing each inner element from the previous row.

TimeComplexity: O(n^2)

SpaceComplexity: O(n^2)

""" 0118.1 - Pascal's Triangle - Solution 1 - Iterative Row Building """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def generate(self, numRows: int) -> List[List[int]]:
        """Generate Pascal's Triangle Function"""
        triangle = []

        for row_num in range(numRows):
            row = [1] * (row_num + 1)

            for j in range(1, row_num):
                row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j]

            triangle.append(row)

        return triangle


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().generate(5))   # [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
    print(Solution().generate(1))   # [[1]]


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Using Zip on Previous Row

Build each new row by zipping the previous row with a shifted version of itself. The sum of each pair gives the inner elements, and we prepend and append 1 to complete the row.

TimeComplexity: O(n^2)

SpaceComplexity: O(n^2)

""" 0118.2 - Pascal's Triangle - Solution 2 - Using Zip on Previous Row """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def generate(self, numRows: int) -> List[List[int]]:
        """Generate Pascal's Triangle Function"""
        triangle = [[1]]

        for _ in range(1, numRows):
            prev = triangle[-1]
            row = [1] + [a + b for a, b in zip(prev, prev[1:])] + [1]
            triangle.append(row)

        return triangle


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().generate(5))   # [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
    print(Solution().generate(1))   # [[1]]


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0118 - Pascal's Triangle

Solution 1 - Iterative Row Building

Solution 2 - Using Zip on Previous Row