Sponsored
Sponsored
This approach involves generating Pascal's Triangle row by row using an iterative method. The first row is initialized with [1], and for each subsequent row, the first and last element are always 1. The intermediate elements are calculated as sums of appropriate elements from the previous row.
Time Complexity: O(numRows^2) due to the nested loop structure.
Space Complexity: O(numRows^2) as we store all elements of the triangle.
1def generate(numRows):
2 triangle = []
3 for i in range(numRows):
4 row = [1] * (i + 1)
5 for j in range(1, i):
6 row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
7 triangle.append(row)
8 return triangle
9
10if __name__ == '__main__':
11 numRows = 5
12 result = generate(numRows)
13 for row in result:
14 print(row)
15This Python function constructs Pascal's Triangle by initializing each row with 1s, then updating middle values using the sum of two values from the previous row. It returns a list of lists representing the triangle.
This approach constructs Pascal's Triangle using recursion by calculating each value based on the combination formula. The values on the edges are always 1, and other values are calculated as combinatorial numbers derived recursively.
Time Complexity: O(numRows^3) due to recursive calls, not optimal.
Space Complexity: O(numRows^2) for storing the triangle.
1
In Python, a combination function computes each element of the triangle recursively using combinatorial logic. Each call calculates a combination's value, rapidly constructing Pascal's Triangle row by row.