# 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%28k%29-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)\\>)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/dynamic_programming/pascals-triangle-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.