---
tags: data_structure_python
---

# Pascal's Triangle II <img src="https://img.shields.io/badge/-easy-brightgreen">

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.

Note that the row index starts from 0.

<ins>**Example:**</ins>

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

**Follow up:**

Could you optimize your algorithm to use only O(k) extra space?

## Solution

### Solution 1: Iterative

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        row, tmp = [1], [1]
        for i in range(1, rowIndex+2):
            row = [1]*i
            for j in range(0, len(tmp)-1):
                row[j+1] = tmp[j] + tmp[j+1]
            tmp = row
        return row

### Solution 2: Recursive

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0:
            return [1]
        elif rowIndex == 1:
            return [1,1]
        else:
            prev = self.getRow(rowIndex-1)
            curr = [1]*(rowIndex + 1)
            for i in range(len(curr)-2):
                curr[i+1] = prev[i] + prev[i+1]
            return curr