Pascal's Triangle

Patrick Leaton
Published: Dec. 18, 2021, 8:28 p.m.
Problem Description

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

 

The description was taken from https://leetcode.com/problems/pascals-triangle/.

Problem Solution

#O(N^2) Time, O(N^2) Space
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        dp = [[1]]
       
        for row in range(1, numRows):
            dp.append([1] * (row + 1))
            for col in range(1, len(dp[row])-1):
                dp[row][col] = dp[row-1][col-1] + dp[row-1][col]
       
        return dp

Problem Explanation

This problem falls into the category of finding very specific paths.

Similar problems also in this category would be Unique Paths, Minimum Falling Path Sum, and Triangle.

Like these other problems, to solve this problem, we can break the overall problem into subproblems that take form within each individual cell from the input.  For each cell, we will look at each possible cell we could have arrived at the current cell from and then make our decision based on what is in these previous cells.

What we can do is build this triangle one row at a time.  We will fill the first and last position of each row with a one, as shown in the illustration from the problem description.  For each cell besides the first and last, we will increment it by both the value within the same column but in the previous row and the cell in the previous column but in the previous row.

1     
1            1           
1    2    1   

Let's start by initializing our dp matrix with the peak of the triangle.

        dp = [[1]]

 

Then, for each row starting from the second, we will append a row of ones.  

This will fill the first and last position of the new with a one since we will be overwriting the middle elements within the next step.

            dp.append([1] * (row + 1))

 

For each column cell excluding the first and the last, we will set the current cell's value as the combined values of the top cell and the top-left cell from the row within our dp cache that we created in the previous iteration.

This may be difficult to imagine for the second row, but one thing to note is that the range [1,1] will terminate immediately so no middle columns will be visited in this loop until the third row.

            for col in range(1, len(dp[row])-1):
                dp[row][col] = dp[row-1][col-1] + dp[row-1][col]

 

Once we have finished building our dp triangle, we will return it.

        return dp