Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0118 - Pascal's Triangle
    0118 - Pascal's Triangle
    0118 - Pascal's Triangle
    0118 - Pascal's Triangle

    0118 - Pascal's Triangle

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/pascals-triangle/

    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(n2)TimeComplexity: O(n^2)TimeComplexity:O(n2)
    SpaceComplexity:O(n2)SpaceComplexity: O(n^2)SpaceComplexity:O(n2)

    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(n2)TimeComplexity: O(n^2)TimeComplexity:O(n2)
    SpaceComplexity:O(n2)SpaceComplexity: O(n^2)SpaceComplexity:O(n2)
    """ 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()

    """ 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()