Pascal's Triangle II

Simulation Array

Problem

Given an integer rowIndex, return the rowIndexth row of the Pascal's triangle.

Notice that the row index starts from 0.

For example:

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

Thought Process

• All we have to do is generate all rows up to the row that is given. We can do this by applying the algorithm we used in Pascal Triangle I

Solution

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        
        if rowIndex < 0:
            return []
        
        matrix = [[1]]
        
        for i in range(1,rowIndex+1):
            row = [1]
            for j in range(1,i):
                row.append(matrix[i-1][j-1] + matrix[i-1][j])
            row.append(1)
            matrix.append(row)
        return matrix[rowIndex]

Key Facts

• Where this problem is different from Pascal's Triangle I is in the input. The input here is indicating which row to generate, and this is 0 based i.e. k=0 corresponds to row 1.

• Since we are generating the matrix up until the row that we want, we need the first for-loop's range to go to rowIndex + 1 since this is 0 based.

Time Complexity

• Time:$O(m*n)$because we have to generate every row and column up until rowIndex

• Space:$O(m*n)$ because we a matrix of rows and columns.