"""
TC: O(n^2)

"""
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if not numRows:
            return []
        
        res = [[1]]
        
        for i in range(1, numRows):
            tmp = [1] * (len(res[-1]) + 1) 
            
            for j in range(1, len(tmp) - 1):
                tmp[j] = res[-1][j - 1] + res[-1][j]
                
            res.append(tmp)
            
        return res

"""
TC: O(n^2)

"""
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if not numRows:
            return []
        
        res = [[1]]
        
        for i in range(1, numRows):
            tmp = [1] * (len(res[-1]) + 1) 
            
            for j in range(1, len(tmp) - 1):
                tmp[j] = res[-1][j - 1] + res[-1][j]
                
            res.append(tmp)
            
        return res

TC: O(n^2)