Problem Description

The Pascal's Triangle II problem asks you to return the rowIndex-th (0-indexed) row of Pascal's Triangle as a list of integers.

Pascal's Triangle is a triangular array where each number is the sum of the two numbers directly above it. The first row is [1], the second row is [1,1], the third row is [1,2,1], and so on.

• You are given a non-negative integer rowIndex.
• Your task is to construct and return the row at index rowIndex of Pascal's Triangle.
• Constraints:
  • 0 ≤ rowIndex ≤ 33

Thought Process

The most straightforward way to solve this would be to generate the entire Pascal's Triangle up to the given row and then return the required row. However, this is inefficient since we only need one row.

Recognizing the pattern, each value in a row is the sum of two values from the previous row. However, we can optimize memory usage by building only one row at a time and updating it in place, moving from the end of the row to the beginning to avoid overwriting values we still need.

Alternatively, since each element in the row is a binomial coefficient, we could compute each value directly using the formula C(rowIndex, k) for each k from 0 to rowIndex.

Solution Approach

• In-Place Row Construction:
  • Start with a list containing a single 1 (the first row).
  • Iteratively build up to the target row by updating the list from the end to the start at each step.
  • For each step, insert a new 1 at the end (since each row starts and ends with 1).
  • Update the inner elements by summing the two elements above them (from the previous state of the row).
• Direct Binomial Coefficient Calculation:
  • Use the formula C(n, k) = C(n, k-1) * (n-k+1) / k to iteratively compute each element.
  • Initialize the row with 1, then repeatedly compute the next value using the previous one.
  • This avoids the need to build all previous rows and is efficient for small rowIndex values.
• Why In-Place Update?
  • It saves space by not storing all previous rows.
  • Updating from the end to the start ensures we don't overwrite values we still need for the current calculation.

Code Implementation

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

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row = {1};
        for (int i = 1; i <= rowIndex; ++i) {
            row.push_back(1);
            for (int j = i - 1; j > 0; --j) {
                row[j] += row[j - 1];
            }
        }
        return row;
    }
};
      

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        row.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            row.add(1);
            for (int j = i - 1; j > 0; j--) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }
        return row;
    }
}
      

var getRow = function(rowIndex) {
    let row = [1];
    for (let i = 1; i <= rowIndex; i++) {
        row.push(1);
        for (let j = i - 1; j > 0; j--) {
            row[j] += row[j - 1];
        }
    }
    return row;
};
      

Example Walkthrough

Let's walk through an example with rowIndex = 3:

• Start with row = [1]
• First iteration (i = 1): append 1 → [1, 1]
• Second iteration (i = 2): append 1 → [1, 1, 1]
  • Update: row[1] += row[0] → row[1] = 2 → [1, 2, 1]
• Third iteration (i = 3): append 1 → [1, 2, 1, 1]
  • Update: row[2] += row[1] → row[2] = 3
  • Update: row[1] += row[0] → row[1] = 3
  • Result: [1, 3, 3, 1]

Final output for rowIndex = 3 is [1, 3, 3, 1].

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n²), since we'd generate all rows up to rowIndex.
  • Space Complexity: O(n²) if storing all rows, O(n) if only storing the current row.
• Optimized in-place approach:
  • Time Complexity: O(n²), as each row requires up to n updates.
  • Space Complexity: O(n), since only one row is stored and updated in place.
• Binomial coefficient approach:
  • Time Complexity: O(n), as each value is computed directly.
  • Space Complexity: O(n), for the output row.

For rowIndex ≤ 33, all approaches are efficient, but the in-place or binomial methods are most elegant.

Summary

The key insight is that we can build Pascal's Triangle rows efficiently by updating a single list in place, moving from the end to the start to avoid overwriting values. Alternatively, using the binomial coefficient formula lets us compute each value directly. Both approaches are optimal for this problem, using O(n) space and efficient time. This solution highlights how understanding the underlying mathematical structure can greatly simplify the implementation.