Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5

Output:

[
      [ 1 ],
     [ 1, 1 ],
    [ 1, 2, 1 ],
   [ 1, 3, 3, 1 ],
  [ 1, 4, 6, 4, 1 ]
]

Solution

from typing import List

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        result = []

        for i in range(numRows):
            newList = [1] * (i+1)
            for j in range(1, len(newList) - 1):
                newList[j] = result[i-1][j-1] + result[i-1][j]
            result.append(newList)

        return result

Test Cases

test = Solution()
answer = test.generate(0)
assert answer == []
answer = test.generate(1)
assert answer == [[1]]
answer = test.generate(2)
assert answer == [[1],[1,1]]
answer = test.generate(5)
assert answer == [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
print('All Passed!')

Big O Analysis

Space Complexity: O(1)

Time Complexity: O(N²)