LeetCode 119. Pascal’s Triangle II

Description

https://leetcode.com/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 1:

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

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

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

Constraints:

  • 0 <= rowIndex <= 33

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

Explanation

One approach we can do is that we can provide row 0 and row 1 as the base case, then infer the 2 to the “rowIndex” rows.

Python Solution

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        result = []
        
        rows = {}
        
        
        rows[0] = [1]
        rows[1] = [1, 1]
        
        if rowIndex == 0:
            return rows[0]
        
        if rowIndex == 1:
            return rows[1]
        
        
        for row in range(2, rowIndex + 1):
            n = row + 1       
            rows[row] = [None for i in range(n)]
            rows[row][0] = 1
            rows[row][row] = 1

            for i in range(1, row):
                rows[row][i] = rows[row - 1][i - 1] + rows[row - 1][i]

        return rows[rowIndex]
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.