118. Pascal's Triangle

https://leetcode.com/problems/pascals-triangle/

Problem

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 O(n^2)

Edge Cases

1. Input is 0 (asking for 0 rows of Pascal) Given the output format is asking us to return an array, for 0 we can return an empty array return []

2. Input is 1 (asking for 1 row of Pascal) This depends on how I create the list of Pascal, but I plan to create an iterative solution using the second row, therefore I create a separate case for this input. So when the input is 1, I will return the first row exclusively in a list return [[1]]

Iterative Solution (Dynamic Programming)

So if n doesn't fall into any of the above edge cases, we can start with the second row, and iterate until our solution is the length of n. So to generate Pascal's Triangle iteratively, we simply take the previous row and use it to generate the next row.

Therefore, if we start using the second row, we begin with [[1],[1,1]]. We can then generate elements of the new row by summing neighbouring elements of the previous row and appending to create a new row.

# PSEUDOCODE
new_row = [1]

# Generate new elements of the row using the previous row
last_row = triangle[-1]
i = 0
while i + 1 < len(last_row):
    new_element = last_row[i] + last_row[i+1]  # sum neighbouring elements
    new_row.append(new_element)
    i += 1
triangle.append(new_row)

So this iterative generation happens until the length of our triangle array is actually the same as the input, n. So coming together, the solution looks like this:

def generate(n):
    # Edge Cases
    # n = 0
    if n == 0:
        return []  # return empty list
    # n = 1
    elif n == 1:
        return [[1]]  # return list with 1 row
        
    # else n > 1
    triangle = [[1], [1, 1]]  # So our triangle begins like this with 2 rows
    while len(triangle) != n:
        last_row = triangle[-1]
        new_row = [1]  # new row starts with 1
        i = 0
        # generate new row
        while i + 1 < len(triangle):
            new_row.append(last_row[i] + last_row[i+1])
            i += 1
        # don't forget to add 1 to the end of the row
        new_row.append(1)
        triangle.append(new_row)  # then add it to the triangle
    
    return triangle