Skip to content

119. Pascal's Triangle II

Difficulty Topics

Description

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?

Solution

pascals-triangle-ii.py
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        t = [[1], [1, 1]]

        for index in range(2, rowIndex + 1):
            tt = t[-1]
            tmp = [1] + [0] * (index - 1) + [1]
            for i in range(1, len(tmp) - 1):
                left = tt[i - 1]
                right = tt[-1] if i + 1 >= len(tt) else tt[i]
                tmp[i] = left + right

            t.append(tmp)

        return t[rowIndex]
pascals-triangle-ii.cpp
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        int n = rowIndex+1;
        vector<int> tri(n,0);
        tri[0] = 1;


        for (int i = 1; i < n; i++){
             for (int j = i; j > 0; j--){
                 tri[j] += tri[j-1];
             }
        }



        return tri;

    }
};