119. Pascal's Triangle II

• python3

📎 Problem

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?

Pseduocode

1. Create an array with a single element: [1].
2. In an array of length one greater than the previous, insert the sum of each pair of elements from the previous array.
3. Repeat the above step until the process is complete.

Code

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:

        row = [1]
        
        for i in range(1, rowIndex + 1):
            new_row = [1] * (i + 1)
            for j in range(1, i):
                new_row[j] = row[j - 1] + row[j]
            row = new_row
        
        return row

Result

• Time Complexity : O(n^2)
• Space Complexity : O(1)