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.
In Pascal's triangle, each number is the sum of the two numbers directly above it.
Example:
1
Input:
2
3
3
4
Output:
5
[1,3,3,1]
Copied!
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
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,内层循环正序即可
1
class Solution {
2
public List<Integer> getRow(int rowIndex) {
3
List<Integer> row = new ArrayList<>();
4
for (int i = 0; i <= rowIndex; i++) {
5
row.add(0, 1);
6
for (int j = 1; j < i; j++) {
7
row.set(j, row.get(j) + row.get(j + 1));
8
}
9
}
10
return row;
11
}
12
}
Copied!
Same approach - Another One 在末尾加1, 内层循环要从末尾倒序循环
1
class Solution {
2
public List<Integer> getRow(int rowIndex) {
3
List<Integer> res = new ArrayList<Integer>();
4
for (int i = 0; i <= rowIndex; i++) {
5
res.add(1);
6
for (int j = i - 1; j >= 1; j++) {
7
res.set(j, res.get(j - 1) + res.get(j));
8
}
9
}
10
return res;
11
}
12
}
Copied!
O(K) space and O(K) time using Math (1ms 91.55%)
1
class Solution {
2
public List<Integer> getRow(int rowIndex) {
3
Integer[] rowList = new Integer[rowIndex+1];
4
rowList[0] = 1;
5
for(int i=1; i<rowList.length;i++) {
6
rowList[i] = (int)((long)rowList[i-1]*(rowIndex-(i-1))/(i));
7
}
8
return Arrays.asList(rowList);
9
}
10
}
Copied!
O(K) space and O(K^2) (0ms 100%)
1
class Solution {
2
public List<Integer> getRow(int rowIndex) {
3
int[] res = new int[rowIndex+1];
4
res[0] = 1;
5
for(int i=1; i<rowIndex+1; i++)
6
for(int j=i; j>=1; j--)
7
res[j] += res[j-1];
8
List<Integer> list = new ArrayList<> ();
9
for(int n : res) {
10
list.add(n);
11
}
12
return list;
13
}
14
}
Copied!
Traditional 2D DP - storing dp[][] element for each layer - O(n^2) time, and O(n^2) space - (1ms AC)
1
class Solution {
2
public List<Integer> getRow(int rowIndex) {
3
List<Integer> ans = new ArrayList<>();
4
int[][] dp = new int[rowIndex + 1][rowIndex + 1];
5
dp[0][0] = 1;
6
for (int i = 1; i <= rowIndex; i++) {
7
dp[i][0] = 1;
8
dp[i][i] = 1;
9
for (int j = 1; j < i; j++) {
10
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
11
}
12
}
13
for (int k = 0; k <= rowIndex; k++) {
14
ans.add(dp[rowIndex][k]);
15
}
16
return ans;
17
}
18
}
Copied!

Reference

Last modified 1yr ago
Copy link