My 8 lines java solution use ArrayList

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

• ``````for(int j=i-1;j>0;j--)
``````

Cool! I never thought of using a backward order. That successfully avoid creating a new list. Thanks!

• Nice solution!

I have a little modification though. If using LinkedList instead of ArrayList, starting from left will still be okay, because insertion in LinkedList only takes O(1) time. Here is my revised code.

``````public List<Integer> getRow(int rowIndex) {
for (int row = 0; row <= rowIndex; row++) {
for (int i = 1; i < row; i++)
ret.set(i, ret.get(i) + ret.get(i + 1));
}
return ret;
}
``````

Same amount of code. :)

• ret.get(i）是因为你的使用链表现在最坏情况下 O(n) 的时间

• Yes you are right... I missed that part. My apology.

• Nice solution. Thanks for sharing. Can you or anybody else tell me the time complexity? Thanks.

• @ynys I think the time complexity may be O(n^3), because the time complexity may be similar to 1^2 + 2^2 + ... + n^2. Correct me if I am wrong.

• ``````public class Solution {
public List<Integer> getRow(int k) {

List<Integer> a = new ArrayList<Integer>(k+1);

for(int row=1; row <= k; row++){
a.set(0,1);
int curr = 1, prev = 1;
int i=1;
for(; i <= row-1; i++){
curr = a.get(i);
a.set(i, curr + prev);
prev = curr;
}