# Pascal's Triangle II

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

Note that the row index starts from 0.

![](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]
```

**Follow up:**

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

## Analysis

**Dynamic Programming**

Same as Pascal's Triangle I, just need to use current row and previous row in order to get O(k) space complexity.

**Math**

Or using math ([https://leetcode.com/problems/pascals-triangle-ii/discuss/38513/My-clean-O(k)-java-solution?orderBy=most\_votes\\](https://leetcode.com/problems/pascals-triangle-ii/discuss/38513/My-clean-O\(k\)-java-solution?orderBy=most_votes%29\\):

row `k` of Pascal's Triangle:

`[C(k,0), C(k,1), ..., C(k, k-1), C(k, k)]`

and

`C[k,i] = C[k,i-1]*(k-i+1)/i`

## Solution

O(K) space O(K^2) time (3ms 11.27%) - 在首位加`1`，内层循环正序即可

```java
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        for (int i = 0; i <= rowIndex; i++) {
            row.add(0, 1);
            for (int j = 1; j < i; j++) {
                row.set(j, row.get(j) + row.get(j + 1));
            }
        }
        return row;
    }
}
```

Same approach - Another One 在末尾加`1`， 内层循环要从末尾倒序循环

```java
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i <= rowIndex; i++) {
            res.add(1);
            for (int j = i - 1; j >= 1; j++) {
                res.set(j, res.get(j - 1) + res.get(j));
            }
        }
        return res;
    }
}
```

O(K) space and O(K) time using Math (1ms 91.55%)

```java
class Solution {
        public List<Integer> getRow(int rowIndex) {
            Integer[] rowList = new Integer[rowIndex+1];
            rowList[0] = 1;
            for(int i=1; i<rowList.length;i++) {
                rowList[i] = (int)((long)rowList[i-1]*(rowIndex-(i-1))/(i));
            }
            return Arrays.asList(rowList);
        }
    }
```

O(K) space and O(K^2) (0ms 100%)

```java
class Solution {
    public List<Integer> getRow(int rowIndex) {
        int[] res = new int[rowIndex+1];
        res[0] = 1;
        for(int i=1; i<rowIndex+1; i++)
            for(int j=i; j>=1; j--)
                res[j] += res[j-1];
        List<Integer> list = new ArrayList<> ();
        for(int n : res) {
            list.add(n);
        }
        return list;
    }
}
```

Traditional 2D DP - storing dp\[]\[] element for each layer - O(n^2) time, and O(n^2) space - (1ms AC)

```java
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> ans = new ArrayList<>();
        int[][] dp = new int[rowIndex + 1][rowIndex + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= rowIndex; i++) {
            dp[i][0] = 1;
            dp[i][i] = 1;
            for (int j = 1; j < i; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }
        for (int k = 0; k <= rowIndex; k++) {
            ans.add(dp[rowIndex][k]);
        }
        return ans;
    }
}
```

## Reference

Wikipedia: \[Pascal's Triangle]\(\[[https://en.wikipedia.org/wiki/Pascal's\_triangle\](https://en.wikipedia.org/wiki/Pascal's\_triangle)\\](https://en.wikipedia.org/wiki/Pascal's_triangle]\(https://en.wikipedia.org/wiki/Pascal's_triangle\)/))