Leetcode 118: Pascal’s Triangle

https://leetcode.com/problems/pascals-triangle/

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Code

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        if numRows == 0:
            return []
        
        res = [[1]]
        for i in xrange(2, numRows+1):
            new_row = [0] * i
            for j in xrange(i):
                if j == 0:
                    new_row[j] = 1
                elif j == i-1:
                    new_row[j] = 1
                else: 
                    new_row[j] = res[-1][j-1] + res[-1][j]
            res.append(new_row)
            
        return res   

Idea

Each element is the sum of adjacent elements in the above line. That’s how Pascal’s Triangle is defined: https://en.wikipedia.org/wiki/Pascal%27s_triangle