Leetcode 118: Pascal’s Triangle

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

118. Pascal’s Triangle 

  • Total Accepted: 103611
  • Total Submissions: 290013
  • Difficulty: Easy
  • Contributors: Admin

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

[
     [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

 

 

Leave a comment

Your email address will not be published. Required fields are marked *