Pascals Triangle - Leetcode Solution

Problem Statement:

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

Example:

Input: 5

Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Solution:

The problem requires us to generate the first numRows of Pascal's triangle. For this, we can iterate through each row from 0 to numRows and generate each row of the Pascal's triangle.

The first and the last element of each row is always 1. For all other elements, we can calculate them based on the elements in the previous row. Specifically, the value of element i in row j is equal to the sum of element i-1 and i in row j-1.

The solution approach can be summarized in the following steps:

1. Create an empty 2D list.
2. Iterate through each row from 0 to numRows.
3. If the current row is the first row, then add [1] to the 2D list.
4. If the current row is not the first row: a. Create an empty list. b. Append 1 to the list. c. Iterate through each element in the previous row (except the first and last elements): i. Calculate the value of the current element using the formula mentioned above. ii. Append the value to the list. d. Append 1 to the list. e. Add the list to the 2D list.
5. Return the 2D list.

Time Complexity:

The time complexity is O(numRows^2) because we are iterating through numRows for generating each row of the Pascal's triangle.

Space Complexity:

The space complexity is also O(numRows^2) because we are storing all the elements of the Pascal's triangle in a 2D list.

Python Code:

def generate(numRows: int) -> List[List[int]]: triangle = [] for i in range(numRows): row = [] if i == 0: row = [1] else: prev_row = triangle[i-1] row.append(1) for j in range(1, i): row.append(prev_row[j-1] + prev_row[j]) row.append(1) triangle.append(row) return triangle

Note:

Here, we are using type hints for function parameters and return values. Also, we are importing the List type from the typing module which is used for type hints.

1