119_Pascal's Triangle II

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.

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

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

Input:
 3

Output:
 [1,3,3,1]

Solution:

Idea:

• Loop row by row, only save the row above and the current row

Time complexity: $O(k^2)$

Space complexity: $O(k)$

def getRow(self, rowIndex):
    """
    :type rowIndex: int
    :rtype: List[int]
    """
    row_above = []
    for i in range(rowIndex+1) :
        row = [1]*(i+1)
        for j in range(1, i):
            row[j] = row_above[j-1] + row_above[j]
        row_above = row[:]
    return row

Another

result = []
for i in range (rowIndex + 1):
    result = [1] + result
    for j in range (1,len(result)-1):
        result[j] += result[j+1]
return result