Kth Row of Pascal's Triangle
Given an index k, return the kth row of the Pascal’s triangle.
Pascal’s triangle : To generate A[C] in row R, sum up A’[C] and A’[C-1] from previous row R - 1.
Example:
Input : k = 3
Return : [1,3,3,1]
NOTE : k is 0 based. k = 0, corresponds to the row [1].
Note:Could you optimize your algorithm to use only O(k) extra space?
public class Solution {
public int[] getRow(int A) {
int[] ans = new int[A + 1];
int nC1 = A;
int r = 1;
for (int i = 0; i <= A; i++) {
if (i == 0 || i == A)
ans[i] = 1;
else {
ans[i] = nC1;
nC1 = nC1 * (A - r) / (1 + r);
r++;
}
}
return ans;
}
}
Last updated