LeetCode #119 Pascal’s Triangle II
Problem
Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle.
Note that the row index starts from 0.
In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 3
Output: [1,3,3,1]Follow up:
Could you optimize your algorithm to use only O(k) extra space?
Solution
Like #118, we also use dynamic programming approach for calculating elements of current level. But because it needs to use the element at matrix[row-1][col-1], our iterating direction should be from end to front.
Complexity
As we explained in #118, line 20 may be run 1 + 2 + … + k = O(k²) time which k is rowIndex. Hence, it’s time complexity is O(k²).
However, we only allocate a list with n+1 size so space complexity is only O(k).
