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;
}