#119

Easy

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Pascal's Triangle II

Compute the specific row of Pascal's Triangle using efficient state transition dynamic programming with array-based updates.

array dynamic programming

Problem Statement

Given a non-negative integer rowIndex, return the rowIndex-th row (0-indexed) of Pascal's Triangle. Each element in the row is the sum of the two elements directly above it in the previous row.

For example, rowIndex = 3 should return [1,3,3,1], and rowIndex = 0 should return [1]. Implement an approach that efficiently calculates the row using array-based dynamic programming and proper state transitions.

Examples

Example 1

Input: rowIndex = 3

Output: [1,3,3,1]

Example details omitted.

Example 2

Input: rowIndex = 0

Output: [1]

Example details omitted.

Example 3

Input: rowIndex = 1

Output: [1,1]

Example details omitted.

Constraints

0 <= rowIndex <= 33

Solution Approach

Iterative Array Update

Initialize an array of size rowIndex + 1 with 1s and iterate from the second row to rowIndex. Update each element from end to start to avoid overwriting needed values.

In-Place Dynamic Programming

Use a single array to store current row values, modifying elements in place. For each row, update elements from right to left based on the sum of the current element and the one before it.

Space Optimization

Avoid constructing the entire triangle by maintaining only one array for the current row. This reduces space complexity to O(rowIndex) while still using the standard state transition logic.

Complexity Analysis

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

Time complexity is O(rowIndex^2) due to nested iteration to update each element, and space complexity is O(rowIndex) because only a single row array is maintained.

What Interviewers Usually Probe

Check if you can compute only the requested row without building the full triangle.
Expect discussion on in-place updates and avoiding overwriting previous row values.
Consider edge cases like rowIndex = 0 or rowIndex = 1 to confirm correct base cases.

Common Pitfalls or Variants

Common pitfalls

Overwriting elements from left to right, which corrupts intermediate sums.
Attempting to build the full Pascal's Triangle when only one row is needed.
Ignoring base cases, leading to index out-of-bounds errors or incorrect first row values.

Follow-up variants

Return the triangle up to rowIndex instead of only one row.
Compute a specific element in rowIndex-th row using combinatorial formula.
Modify the algorithm to handle large rowIndex values efficiently with BigInteger types.

FAQ

What is the best approach for Pascal's Triangle II using dynamic programming?

Use a single array updated from right to left, applying state transitions to compute only the requested row.

How do I handle rowIndex = 0 or rowIndex = 1?

Return [1] for rowIndex = 0 and [1,1] for rowIndex = 1, handling base cases before iteration.

Can I reduce space usage when generating Pascal's Triangle II?

Yes, by maintaining a single array and updating it in place, space complexity is O(rowIndex).

Why does updating from left to right fail?

It overwrites values needed for computing subsequent elements, breaking the state transition logic.

Is there a combinatorial formula alternative?

Yes, each element can be computed using C(rowIndex, k), but iterative DP is often simpler for interviews.

terminal

Solution

Solution 1: Recursion

We create an array $f$ of length $rowIndex + 1$, initially all elements are $1$.

1

2

3

4

5

6

7

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        f = [1] * (rowIndex + 1)
        for i in range(2, rowIndex + 1):
            for j in range(i - 1, 0, -1):
                f[j] += f[j - 1]
        return f

Continue Practicing

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