Leetcode:118. Pascal's Triangle

This is an explanation of the code of Leetcode:118. Pascal's Triangle.

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

        for i in range(numRows - 1):
            temp = [0] + res[-1] + [0]
            row = []
            for j in range(len(res[-1]) + 1):
                row.append(temp[j] + temp[j + 1])
            res.append(row)
        return res

This code is a solution for generating Pascal's Triangle.

1. res = [[1]]initilizes the first row of the Pascal's Triangle, which is always [1].
2. for i in range(numRows - 1): iterates (numRows - 1) times. This is because the first row is already initilized, so the only thing we need to do is generating the remaining rows.
3. temp = [0] + res[-1] + [0] is a key step. It takes the last generated row (res[-1]) and pads it with a zero at both ends. For example, if res[-1] is [1, 1], temp becomes [0, 1, 1, 0]. This padding simplifies the calculation for the next row because the first and last elements of any row are always 1, which are generated by 0 + 1 and 1 + 0.
4. row = [] initializes an empty list for the new row.
   for j in range(len(res[-1]) + 1): iterates through the elements to be calculated for the new row. The new row will always have one more element than the previous row.
   row.append(temp[j] + temp[j + 1]) calculates each element of the new row by summing adjacent elements from the temp list. For example, using temp = [0, 1, 1, 0], the new row would be calculated as:
   ・temp[0] + temp[1] -> 0 + 1 = 1
   ・temp[1] + temp[2] -> 1 + 1 = 2
   ・temp[2] + temp[3] -> 1 + 0 = 1
   This results in the row [1, 2, 1].
5. res.append(row) adds the newly calculated row to the res list.
6. return res returns the complete Pascal's Triangle.
   The time complexity is O(N**2). This is because the outer loop runs numRows(=N) times, and the inner loop runs i times each iteration (which is at most N times). In total, this results in approximately N*N calculations.
   I refered to https://www.youtube.com/watch?v=nPVEaB3AjUM and gemini for the explanation.