#118

Easy

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Pascal's Triangle

Generate the first numRows of Pascal's Triangle using dynamic programming with clear state transitions and array manipulation.

array dynamic programming

Problem Statement

Given an integer numRows, generate the first numRows of Pascal's Triangle. Each row should be represented as a list of integers where the first and last elements are 1, and every other element is the sum of the two numbers directly above it from the previous row.

Return the result as a list of lists, where each inner list represents a row of Pascal's Triangle. For example, for numRows = 5, the output should be [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]. Ensure your implementation handles the boundary conditions correctly and constructs the triangle iteratively using dynamic programming.

Examples

Example 1

Input: numRows = 5

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

Example details omitted.

Example 2

Input: numRows = 1

Output: [[1]]

Example details omitted.

Constraints

1 <= numRows <= 30

Solution Approach

Iterative Dynamic Programming

Start with a result array containing the first row [1]. For each subsequent row, initialize a new list with 1 at the beginning and end. Fill the interior elements using the sum of the two elements directly above in the previous row. Append the completed row to the result. Repeat until numRows are generated. This leverages state transition dynamic programming to build each row efficiently.

Handling Edge Cases

For numRows = 1, immediately return [[1]]. Ensure that the first and last elements of every row remain 1. Dynamic programming logic must account for these boundaries to avoid index errors or incorrect sums, which are common mistakes in Pascal's Triangle problems.

Space Optimization

Although storing all rows is typical, for interview scenarios, one could optimize by keeping only the previous row to generate the current row. This reduces space usage from O(n^2) to O(n), while the core state transition dynamic programming principle remains intact.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(numRows^2) because each row i contains i elements, and we compute each sum once. Space complexity is O(numRows^2) if storing all rows, or O(numRows) if only keeping the previous row for computation.

What Interviewers Usually Probe

Asks if you can explain why each element is the sum of the two above.
Wants a clear iterative or dynamic programming solution, not recursion.
May probe how you handle boundaries or optimize space for large numRows.

Common Pitfalls or Variants

Common pitfalls

Forgetting to place 1 at the start and end of each row.
Incorrectly summing elements causing off-by-one errors in the triangle.
Attempting recursion without memoization, leading to unnecessary complexity.

Follow-up variants

Generate only the nth row without constructing the full triangle using optimized DP.
Return Pascal's Triangle modulo a given number for very large values.
Compute triangle diagonals or specific positions efficiently using combinatorial formulas.

FAQ

What is the core pattern used in Pascal's Triangle problem?

The main pattern is state transition dynamic programming, where each row is derived from the previous by summing adjacent elements.

Can Pascal's Triangle be generated recursively?

Yes, but recursion without memoization is inefficient and can lead to repeated computations; iterative DP is preferred.

How do I handle the first and last elements in each row?

Always set the first and last elements to 1 explicitly; only sum elements in between using the previous row.

What is the time complexity of generating numRows rows?

Time complexity is O(numRows^2) since row i has i elements and each element is computed once.

Is it possible to optimize space while generating Pascal's Triangle?

Yes, by keeping only the previous row to compute the current row, space can be reduced to O(numRows).

terminal

Solution

Solution 1: Simulation

We first create an answer array $f$, then set the first row of $f$ to $[1]$. Next, starting from the second row, the first and last elements of each row are $1$, and for other elements $f[i][j] = f[i - 1][j - 1] + f[i - 1][j]$.

1

2

3

4

5

6

7

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        f = [[1]]
        for i in range(numRows - 1):
            g = [1] + [a + b for a, b in pairwise(f[-1])] + [1]
            f.append(g)
        return f

Continue Practicing

#119 pascals triangle ii #120 triangle #121 best time to buy and sell stock