Pascal's Triangle

How it works

We directly apply the defining property of Pascal's Triangle: each interior element equals the sum of the two elements above it. The first and last elements of every row are always 1. We build row by row, referencing the previous row for the sums.

Steps

1. Initialize a 2D list where row i has i + 1 elements, all set to 1.
2. For each row from index 2 onward:
   • For each interior position j (not the first or last):
     • Set res[i][j] = res[i - 1][j - 1] + res[i - 1][j].
3. Return the completed triangle.

Complexity

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

Things to watch for

Off-by-One Errors with Row Indexing

Pascal's Triangle is often 0-indexed, so row 0 is [1], row 1 is [1, 1], and so on. Confusing 0-indexed and 1-indexed row numbering leads to generating one too many or one too few rows. Always clarify whether numRows means the count of rows or the index of the last row.

Forgetting Edge Elements Are Always 1

The first and last elements of every row are always 1. When building rows iteratively, only the interior elements (positions 1 through i-1 for row i) need to be computed as sums. Attempting to compute edge elements using the sum formula causes index-out-of-bounds errors.

from typing import List

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

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res(numRows);

        for (int i = 0; i < numRows; i++) {
            res[i].resize(i + 1);
            res[i][0] = res[i][i] = 1;
            for (int j = 1; j < i; j++){
                res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
            }
        }
        return res;
    }
};