> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/dynamic_programming/pascals-triangle-ii.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.