Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

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

 

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

 

Constraints:

  • 0 <= rowIndex <= 33

 

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?





 class Solution:
    def getRow(self, rowIndex: int) -> List[int]:


        # def value(i, j, memory=None):
        #     if (i,j) in memory:
        #         return memory[(i,j)]
        #     if i == j or j == 0:
        #         return 1
        #     memory[(i,j)] = value(i-1, j-1, memory) + value(i-1, j, memory)
        #     return memory[(i,j)]
        # memory = {}
        # l = []
        # for i in range(rowIndex+1):
        #     l.append(value(rowIndex, i, memory))
        # return l

        from functools import lru_cache
        @lru_cache()
        def value(i, j):
            if i == j or j == 0:
                return 1
            return value(i-1, j-1) + value(i-1, j)

        l = []
        for i in range(rowIndex+1):
            l.append(value(rowIndex, i))
        return l

Random Note


From python 3.7 dict guarantees that order will be kept as they inserted, and popitem will use LIFO order but we need FIFO type system. so we need OrderedDict which have popIten(last = T/F) for this req. One thing, next(iter(dict)) will return the first key of the dict