Pascal's Triangle

Simulation Array

Problem

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

For example:

Input: numRows = 5
Output:
[
     [1],
     [1,1],
     [1,2,1],
     [1,3,3,1],
     [1,4,6,4,1]
]

Thought Process:

• How do we generate the specific sizes of the inner arrays thats specific to each row?

  • By having a seperate array/list for each row in the matrix and appending this list to the overall matrix.

• How would we fill in the numbers for the indices that don't have a number directly above them to the left?

  • The first and last number in a row will have a "1" appended to them so we don't have to worry about this case.

• How do we generate the specific numbers for each indices?

  • For rows >= the 2nd row, the only indices that are needed for numbers are the middle indices, excluding the first and last numbers in the row (since we append these at the beginning and the end). We can generate these middle numbers using matrix[i][j] = matrix[i-1][j-1] + matrix[i-1][j].

• Which row do we start at?

  • We start at the second row

Solution

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows <= 0:
            return []
        
        matrix=[[1]] 
        for i in range(1,numRows):
            row = [1]
            for j in range(1,i):
                row.append(matrix[i-1][j-1]+matrix[i-1][j])
            row.append(1)
            matrix.append(row)
        return matrix
            

Key Facts

• Initially, we just have a matrix variable with a single row in it, and from this, we append new rows to it with the numbers generated inside.

• We need 2 for loops: One for loop to loop through the rows and the second for loop to loop through and fill the column indexes with numbers.

• We begin at the second row when looping through the rows

Time Complexity

• Time:$O(m*n)$ because we have to go through every row and column in the matrix (two for loops)

• Space:$O(m*n)$ because we have matrix