LeetCode 118 – Pascal's Triangle

Pascal's Triangle is the gentlest possible bottom-up dynamic programming problem: each row is built from the one before it, there is nothing to optimise, and no edge case can really bite. It is on interview lists as a warm-up and as the setup for its follow-up, which is where the actual technique lives.

The problem

Given numRows, return the first numRows rows of Pascal's triangle. Each number is the sum of the two directly above it.

numRows = 5

        [1]
       [1,1]
      [1,2,1]
     [1,3,3,1]
    [1,4,6,4,1]

numRows = 1  -> [[1]]
numRows = 0  -> []

The rule, and where it does not apply

row[0] = row[last] = 1                         the edges
row[c] = previous[c-1] + previous[c]           everything else

The edges are not a special case bolted on — they are where the rule runs out of inputs. Position 0 has nothing above-left and the last position has nothing above-right, so the general formula would be reading off the end of the previous row. Filling them with 1 is the boundary condition, exactly like the top row and left column in Unique Paths — and in fact this is Unique Paths' table, rotated.

Row r has r + 1 entries. Getting that off by one is the only real way to go wrong here.

Java

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();

        for (int row = 0; row < numRows; row++) {
            List<Integer> current = new ArrayList<>(row + 1);   // row r has r+1 entries

            for (int col = 0; col <= row; col++) {
                if (col == 0 || col == row) {
                    current.add(1);                              // the edges
                } else {
                    List<Integer> previous = triangle.get(row - 1);
                    current.add(previous.get(col - 1) + previous.get(col));
                }
            }

            triangle.add(current);
        }

        return triangle;
    }
}

numRows = 0 falls out with no guard: the loop never runs and an empty list is returned. Reaching for an explicit check there is a small sign of not trusting the loop bounds.

Sizing the inner list with new ArrayList<>(row + 1) avoids the growth reallocation. Trivial here, and the habit is worth having when the sizes are not tiny.

Python

class Solution:
    def generate(self, numRows: int) -> list[list[int]]:
        triangle: list[list[int]] = []

        for row in range(numRows):
            current = [1] * (row + 1)                # edges already correct

            for col in range(1, row):                # interior only
                current[col] = triangle[row - 1][col - 1] + triangle[row - 1][col]

            triangle.append(current)

        return triangle

Pre-filling with 1s removes the edge branch entirely — the interior loop runs from 1 to row - 1 and simply does not execute for the first two rows. That is a real simplification rather than a golfing trick: fewer branches, and the boundary condition is stated once in the initialiser instead of tested every iteration.

The zip trick

A well-known Python one-liner per row, worth recognising even if you would not lead with it:

previous     = [1, 3, 3, 1]
[0] + prev   = [0, 1, 3, 3, 1]
prev + [0]   = [1, 3, 3, 1, 0]
zipped sums  = [1, 4, 6, 4, 1]      the next row

Padding with a zero on each side turns the boundary condition into arithmetic — the missing neighbour contributes 0, which is precisely what "there is nothing above-left" means. It is the same observation as the edges, expressed differently, and that is the interesting part rather than the brevity.

Complexity

	Time	Space
Row by row	`O(numRows²)`	`O(numRows²)` output

The triangle has 1 + 2 + … + numRows entries, which is O(numRows²), so producing it cannot be faster than that. The output is the complexity, and there is nothing to improve — which is exactly why problem 119 asks for a single row instead.

Say that connection unprompted. It shows you understand why the follow-up exists rather than treating it as a separate question.

Overflow, if the constraints were looser

LeetCode caps numRows at 30, and the largest entry in row 30 is about 155 million — comfortably inside an int. Row 34 would overflow it.

Worth one sentence: the entries are binomial coefficients and they grow roughly like 2ⁿ, so the row index at which a fixed-width integer gives out is small. Noticing the constraint is doing real work, rather than assuming it is arbitrary, is the habit being rewarded.

The pattern

"Each row from the previous row" is the shape of every bottom-up DP with a one-dimensional state. Unique Paths (62) is this triangle in rectangular coordinates. Pascal's Triangle II (119) keeps only the current row and is where the rolling-array technique has to be done properly. Triangle (120) walks a triangle bottom-up taking minimums.

What the interviewer is checking

That row r has r + 1 entries.
The edges as a boundary condition, not a bolted-on special case.
numRows = 0 and numRows = 1.
That the output size is the complexity, so there is nothing to optimise.
That you connect it to the single-row follow-up.
Whether you check the constraint against integer overflow rather than assuming.