119. Pascal's Triangle II

Problem Statement

link: https://leetcode.com/problems/pascals-triangle-ii/ https://leetcode.cn/problems/pascals-triangle-ii/

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.

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

Input: rowIndex = 3 Output: [1,3,3,1]

Input: rowIndex = 0 Output: [1]

Input: rowIndex = 1 Output: [1,1]

Solution Approach

The solution makes use of a dynamic programming approach, by incrementally building the Pascal’s triangle row-by-row, without storing all the rows.

Algorithm

1. Initialize the result list with the first value as [1].
2. Iteratively compute each row’s values by adding adjacent values from the previous row, starting from the end towards the beginning of the row.
3. After processing each row, append 1 to signify the end of the current row, and repeat until the desired rowIndex is reached.

Implement

    Class Solution:
  def getRow(self, rowIndex: int) -> List[int]:
      res = [1]
      for j in range(rowIndex):
          for i in range(j, 0, -1):
              res[i] = res[i - 1] + res[i]
          res.append(1)
      return res
 

    
    

Twitter  facebook  Email