Leetcode: Pascal’s Triangle

Pascal’s Triangle | LeetCode OJ

This is a fairly simple problem. To create the next row we need to use the values present in the previous row.

1. Initialize the result with the first row
2. To create a new row, find the last row in the result
3. Pair-wise add the element in this row to get the middle element of the new row
4. Add 1 to each end of the new row
5. Append it to result

Remarks:

1. For generating n rows we need to generate O(n²) elements, hence both the time and space complexity are O(n²)

Extension:

1. Print the nth row of the Pascal’s triangle

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        if numRows == 0:
            return []
        res = [[1]]
        for j in range(numRows - 1):
            prev = res[-1]
            next = [1]
            for i in range(len(prev) - 1):
                next.append(prev[i] + prev[i + 1])
            next.append(1)
            res.append(next)
        return res