119. 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?

Solution:

The idea is that in each level, we need to know the previous level first.

Based on the result of the previous level, we insert a 1 at the beginning.

Then, start from the second element, we update its value by adding the value of the next element.

Since the last element has no next element, it will be always 1.

We use linked list to store the numbers so that we can achieve constant space requirement.

The time complexity is O(n²) and the space complexity is O(1).



Code:

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