Pythonic solution with explanation


  • 1
    T

    We start with the 0th row, [1]. Because every row can be built as the sum of the previous rows, we insert dummy zero values on either end of the row to build the next row as sums. The 0th row turns into temp = 0, 1, 0], and we can build the 1st row from that as [temp[0] + temp[1]. temp[1] + temp[2]] = [0 + 1, 1 + 0] = [1, 1].

    Repeating, we prepend and append zeros to get [0, 1, 1, 0], then take pairwise sums to get [1, 2, 1], which is the 2nd row.

    In Python, concatenating two lists is very simple: [1] + [2] = [1, 2]. To get the temp row from the current row, we put temp = [0] + curr + [0].

    The pairwise sums can be written Pythonically as a list comprehension. When we're on row i (e.g., 3) our temp row (e.g., [0, 1, 3, 3, 1, 0]) will have i + 3 (e.g., 6) elements in it. We want the sums of indexes 0 and 1, 1 and 2, ..., i +1 and i + 2. (Repeat examples until you're convinced of this.) Write this as [temp[i] + temp[i+1] for i in range(row + 2)].

    We can repeat this process, only keeping track of the current row to use space efficiently.

    class Solution:
        # @param {integer} rowIndex
        # @return {integer[]}
        def getRow(self, rowIndex):
            curr = [1]
            row = 0
            while (row < rowIndex):
                temp = [0] + curr + [0]
                curr = [temp[i] + temp[i+1] for i in range(row + 2)]
                row += 1
            return curr

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.