< Back




118. Pascal's Triangle

Dynamic programming problem to create Pascal's Triangle, such that for each row, the first and last
elements are 1, but the middle elements are the sum of the values above and above and to the left.

The solution is as follows:


  class Solution:
      def generate(self, numRows: int) -> List[List[int]]:
          if numRows == 1:
              return [[1]]
          elif numRows == 2:
              return [[1], [1, 1]]

          ans = [[1], [1, 1]]

          for i in range(2, numRows):
              curr = [1] * (i + 1)

              for j in range(1, i):
                  curr[j] = ans[i - 1][j - 1] + ans[i - 1][j]

              ans += [curr]

          return ans


_ Time Complexity:

  O(n^2) - Where n is numRows.

_ Space Complexity:

  O(1) - We don't consider the output to be part of the space complexity.