Leetcode: Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

Understand the problem:
The problem is an extension of the Pascal's Triangle I. The mainly difference is it only asks you output the kth row of the triangle. Note that k starts from 0. 

One straight-forward solution is  to generate all rows of the Pascal's triangle until the kth row. In this way the complexity is O(k^2). However the problem asks for using only O(k) extra space. 

Solution:
Note that in the previous solution for Problem I, we only need to results for current and its previous row. That means we only need to maintain these two rows, where the space complexity is still O(k).

Code (Java):

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> prev = new ArrayList<Integer>();
        prev.add(1);
        
        for (int i = 1; i <= rowIndex; i++) {
            List<Integer> result = new ArrayList<Integer>();
            result.add(1);
            for (int j = 1; j <= i - 1; j++) {
                result.add(prev.get(j) + prev.get(j - 1));
            }
            result.add(1);
            
            for (int k = 0; k < prev.size(); k++) {
                prev.set(k, result.get(k));
            }
            prev.add(1);
        }
        
        return prev;
    }
}

Discussion:
For the solution above, it takes O(k) space but takes O(n^3) time because the copy of array operations. We need to think of a better solution.

A better solution:
Note that for a[j] = a[j] + a[j - 1], so for each a[j] we can update a[j] from the last a[j] and a[j - 1]. However, if we don't store the previous result, the updated value will pollute the later on numbers. So one solution is to update each number in the row from end in a backward order.

Code (Java):

public class Solution {
    public List getRow(int rowIndex) {
        List result = new ArrayList();
        result.add(1);
        
        for (int i = 1; i <= rowIndex; i++) {
            result.add(1);
            for (int j = i - 1; j > 0; j--) {
                result.set(j, result.get(j) + result.get(j - 1));
            }
        }
        
        return result;
    }
}