Devin's Blog

Pascals Triangle

2 min read

TARGET DECK: Leetcode FILE TAGS: Easy

Intuition

  • This problem can be solved by filling up the perimeter of the triangle with 1’s, then going row by row, filling up the insides with the previous two values, respectively.
  • However, notice that only two values are ever needed when adding up.
  • When doing top down, the trick is to figure out where the top is.
    • In this case, image the triangle as flipped (rotated 90 degrees).
    • Now, the problem reduces to multi source top down in which you are filling the last row by recursing through all the rest of the possibilities.
    • The idea is:
      • Whenever you go out of bounds, don’t fill the triangle
      • If you have filled the triangle before, then don’t fill it again (same as a DP array).
      • If you don’t go out of bounds, then check if you are on the first or last column of that row. If you are, then fill it with a 1.

Complexity

Runtime

Space

Code

Top Down

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        triangle = [[0] * (row + 1) for row in range(numRows)]
 
        def r(row, col):
            if row < 0 or not (0 <= col < row + 1):
                return 0
            if triangle[row][col] != 0:
                return triangle[row][col]
            if 0 <= col - 1 < row + 1:
                triangle[row][col] = r(row - 1, col - 1) + r(row - 1, col)
            else:
                triangle[row][col] = 1
            return triangle[row][col]
 
        for c in range(numRows): # The last row has numRows columns
            triangle[numRows - 1][c] = r(numRows - 1, c)
        return triangle
  • The “top” in this case is each of the cells on the bottom of the triangle.

Iterative

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        triangle = []
        for row in range(numRows):
            triangle.append([0] * (row + 1))
            triangle[row][0], triangle[row][-1] = 1, 1
        for r in range(2, numRows):
            for c in range(1, r + 1 - 1): # [1, len(triangle[r]) - 1]
                triangle[r][c] = triangle[r - 1][c - 1] + triangle[r - 1][c]
        return triangle

Notes

Cards

START Basic Front: Pascals Triangle Back: For top down, use the bottom of the triangle, and for bottom up, iterate through each row starting from the top of the triangle.

END

References

Graph View