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).