Pascal's Triangle II

How it works

The values in row n of Pascal's Triangle are the binomial coefficients C(n, 0), C(n, 1), ..., C(n, n). We can compute each coefficient incrementally from the previous one using the formula: C(n, k) = C(n, k - 1) * (n - k + 1) / k.

Steps

1. Start with row = [1].
2. For each i from 1 to rowIndex:
   • Compute the next value as row[last] * (rowIndex - i + 1) / i.
   • Append it to the row.
3. Return row.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Integer Overflow in Combinatorics Approach

When computing binomial coefficients using the formula C(n, k) = C(n, k-1) * (n - k + 1) / k, the intermediate multiplication can overflow before the division. Always multiply first and divide immediately, or use long types to hold intermediate results before casting back to int.

Wrong Iteration Direction in Space-Optimized DP

When updating the row in place, iterating from left to right overwrites values that are still needed for subsequent calculations. You must iterate from right to left so that each element is updated using the original (unmodified) values from the previous logical row.

from typing import List

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        row = [1]
        for i in range(1, rowIndex + 1):
            row.append(row[-1] * (rowIndex - i + 1) // i)
        return row

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row = {1};
        for (int i = 1; i <= rowIndex; i++) {
            row.push_back(int(row.back() * 1LL * (rowIndex - i + 1) / i));
        }
        return row;
    }
};