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^{2})