> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/matrix/119pascal-s-triangle-ii.md).

# 119\_Pascal's Triangle II

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.

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

![](https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif)\
In Pascal's triangle, each number is the sum of the two numbers directly above it.

## **Example:**

```
Input:
 3

Output:
 [1,3,3,1]
```

## Solution:

**Idea**:

* Loop row by row, only save the row above and the current row

**Time complexity**: $$O(k^2)$$

**Space complexity**: $$O(k)$$

```python
def getRow(self, rowIndex):
    """
    :type rowIndex: int
    :rtype: List[int]
    """
    row_above = []
    for i in range(rowIndex+1) :
        row = [1]*(i+1)
        for j in range(1, i):
            row[j] = row_above[j-1] + row_above[j]
        row_above = row[:]
    return row
```

Another

```python
result = []
for i in range (rowIndex + 1):
    result = [1] + result
    for j in range (1,len(result)-1):
        result[j] += result[j+1]
return result
```