Question

link

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?

Stats

Frequency 1
Difficulty 2
Adjusted Difficulty
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a math question.

First code below is my code.

Second code is a very concise solution from this blog.

Code

First, my code

public ArrayList<Integer> getRow(int rowIndex) {
    ArrayList<Integer> ans = new ArrayList<Integer>();
    if (rowIndex == 0) {
        ans.add(1);
        return ans;
    }
    int[] nodes = new int[rowIndex + 1];
    nodes[0] = 1;
    for (int k = 1; k <= rowIndex; k++) {
        for (int i = k / 2; i >= 1; i--) {
            if (k % 2 == 0 && i == k / 2)
                nodes[i] = 2 * nodes[i - 1];
            else
                nodes[i] = nodes[i - 1] + nodes[i];
        }
        for (int j = k / 2 + 1; j <= k; j++) {
            nodes[j] = nodes[k - j];
        }
    }
    for (Integer a: nodes) ans.add(a);
    return ans;
}

Second, a better version

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