119. Pascal's Triangle II - Explanation

1. Dynamic Programming (Top-Down)

Intuition

To get row n, we need row n - 1 first. Each row depends on the previous one, with interior elements being the sum of two adjacent elements from above. Recursion naturally models this dependency: we compute the previous row, then build the current row from it.

Algorithm

Base case: If rowIndex == 0, return [1].
Recursively get the previous row.
Start the current row with [1].
For each index from 1 to rowIndex - 1:
- Add prevRow[i - 1] + prevRow[i] to the current row.
Append 1 to complete the row.
Return the current row.

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0:
            return [1]

        curRow = [1]
        prevRow = self.getRow(rowIndex - 1)

        for i in range(1, rowIndex):
            curRow.append(prevRow[i - 1] + prevRow[i])

        curRow.append(1)
        return curRow

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Dynamic Programming (Bottom-Up)

Intuition

We build the entire triangle iteratively from row 0 up to the target row. Each row is constructed using values from the previous row. Though we store all rows, we only need the last one as our answer.

Algorithm

Create a 2D list where row i has i + 1 elements, all initialized to 1.
For each row from index 2 to rowIndex:
- For each interior position j:
  - Set res[i][j] = res[i - 1][j - 1] + res[i - 1][j].
Return res[rowIndex].

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

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Dynamic Programming (Space Optimized - I)

Intuition

We only need the previous row to compute the current row, so we don't need to store the entire triangle. We keep one row at a time and build the next row by adding contributions from adjacent elements.

Algorithm

Start with res = [1].
For each iteration from 0 to rowIndex - 1:
- Create nextRow of size len(res) + 1, filled with 0.
- For each element in the current row, add its value to nextRow[j] and nextRow[j + 1].
- Replace res with nextRow.
Return res.

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

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

4. Dynamic Programming (Space Optimized - II)

Intuition

We can update the row in place by iterating from right to left. This ensures we don't overwrite values we still need. Each element becomes the sum of itself and the element to its left, which matches how Pascal's Triangle is built.

Algorithm

Initialize row with rowIndex + 1 elements, all set to 1.
For each row from 1 to rowIndex - 1:
- Iterate from index i down to 1:
  - Add row[j - 1] to row[j].
Return row.

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

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

5. Combinatorics

Intuition

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.

Algorithm

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

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

Time & Space Complexity

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

Common Pitfalls

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.