Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0119 - Pascal's Triangle II
    0119 - Pascal's Triangle II
    0119 - Pascal's Triangle II
    0119 - Pascal's Triangle II

    0119 - Pascal's Triangle II

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

    Solution 1 - Build Row Iteratively

    Given an integer rowIndex, return the rowIndex-th (0-indexed) row of Pascal's triangle. Build the triangle row by row from row 0 up to rowIndex, where each element is the sum of the two elements directly above it. Return the final row.

    TimeComplexity:O(rowIndex2)TimeComplexity: O(rowIndex^2)TimeComplexity:O(rowIndex2)
    SpaceComplexity:O(rowIndex2)SpaceComplexity: O(rowIndex^2)SpaceComplexity:O(rowIndex2)

    Solution 2 - In-Place Single Row (O(k) Space)

    Optimize space by only maintaining a single row and updating it in-place from right to left. This avoids storing the entire triangle. Each iteration updates the current row by adding adjacent elements from the previous state.

    TimeComplexity:O(rowIndex2)TimeComplexity: O(rowIndex^2)TimeComplexity:O(rowIndex2)
    SpaceComplexity:O(rowIndex)SpaceComplexity: O(rowIndex)SpaceComplexity:O(rowIndex)
    """ 0119.1 - Solution 1 - Build Row Iteratively """

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

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

    def getRow(self, rowIndex: int) -> List[int]:
        """Return the rowIndex-th row of Pascal's Triangle"""
        triangle = [[1]]
        for i in range(1, rowIndex + 1):
            row = [1]
            for j in range(1, i):
                row.append(triangle[i - 1][j - 1] + triangle[i - 1][j])
            row.append(1)
            triangle.append(row)
        return triangle[rowIndex]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().getRow(3))   # [1, 3, 3, 1]
    print(Solution().getRow(0))   # [1]
    print(Solution().getRow(1))   # [1, 1]


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

    """ 0119.2 - Solution 2 - In-Place Single Row (O(k) Space) """

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

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

    def getRow(self, rowIndex: int) -> List[int]:
        """Return the rowIndex-th row of Pascal's Triangle using O(k) space"""
        row = [1] * (rowIndex + 1)
        for i in range(2, rowIndex + 1):
            for j in range(i - 1, 0, -1):
                row[j] += row[j - 1]
        return row


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().getRow(3))   # [1, 3, 3, 1]
    print(Solution().getRow(0))   # [1]
    print(Solution().getRow(1))   # [1, 1]


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