Skip to content

118. Pascals Triangle

Array Dynamic Programming

Problem - Pascals Triangle

Easy

Given an integer numRows, return the first numRows of Pascal's triangle.

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

 

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

 

Constraints:

  • 1 <= numRows <= 30

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        solution = []
        for i in range(numRows):
            current = [1] * (i + 1)

            for j in range(1, i):
                current[j] = solution[i - 1][j - 1] + solution[i - 1][j]

            solution.append(current)
        return solution

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 17.7 MB (58.75%)