Pascal's Triangle LeetCode Solution — Row-by-Row DP

Pascal's Triangle is one of those rare problems where you can literally see dynamic programming happening. LeetCode #118 asks you to generate the first numRows rows of Pascal's triangle, and the rule is beautifully simple: every cell equals the sum of the two cells directly above it. The edges are always 1.

If you have ever struggled with dynamic programming, this is the problem to start with. There are no hidden recurrences, no tricky base cases, and no optimization decisions. The pascals triangle leetcode problem strips DP down to its core principle — building each answer from previously computed answers — and makes that principle visible in a triangle of numbers.

By the end of this walkthrough, you will understand exactly how to generate pascal triangle rows one at a time, why the approach is O(n^2), and how this same "build from smaller" idea powers every DP solution you will ever write.

Given an integer numRows, return the first numRows rows of Pascal's triangle. Row 0 is [1]. Row 1 is [1, 1]. Each subsequent row starts and ends with 1, and every inner element is the sum of the two elements above it from the previous row.

This is the most visual DP problem on LeetCode — it literally shows you the "build from smaller subproblems" principle that every DP solution relies on. Each row is a subproblem whose answer depends only on the row before it. There is no need to look further back, no branching decisions, and no state beyond the previous row.

The output is a list of lists. For numRows = 5, you return [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]. Notice that each row has exactly (rowIndex + 1) elements, and the triangle is symmetric — row[j] equals row[len - 1 - j].

The algorithm is as straightforward as DP gets. Start with row 0, which is just [1]. For every new row, create a list that begins with 1, fills in the inner values by summing adjacent pairs from the previous row, and ends with 1. Append that row to your result and repeat.

Here is the step-by-step logic. For row i (0-indexed), create an empty list. Push 1 as the first element. For each index j from 1 to i-1, set the value to prev[j-1] + prev[j], where prev is the previous row. Push 1 as the last element. That is the entire algorithm.

Why does this work? Because the definition of Pascal's triangle IS the recurrence relation. Cell (i, j) = cell (i-1, j-1) + cell (i-1, j). You do not need to discover or derive the recurrence — the problem statement hands it to you. This is why the problem is such a clean DP introduction.

The code mirrors the algorithm exactly. Initialize a result array with [[1]]. Loop from row 1 to numRows - 1. For each row, build a new array starting with [1], compute inner values from the previous row, append 1 at the end, and push the row into the result.

In Python, the inner loop looks like this: for j in range(1, len(prev)), append prev[j-1] + prev[j]. In JavaScript or TypeScript, the same logic applies — iterate from index 1 to prev.length - 1 and sum the two adjacent elements. The implementation is nearly identical across languages because the logic is so direct.

Time complexity is O(n^2) where n is numRows, because row i has i+1 elements and you compute all of them. Space complexity is also O(n^2) for the output — you are storing every element of every row. There is no way to reduce this because the problem asks you to return all rows.

Let us trace through the algorithm with numRows = 5. Row 0: start with [1]. No inner elements. Result: [[1]]. Row 1: start with [1], no inner elements (prev has length 1), end with [1]. Result: [[1], [1,1]].

Row 2: start with [1]. Inner: prev[0] + prev[1] = 1 + 1 = 2. End with [1]. Row is [1,2,1]. Row 3: start with [1]. Inner: prev[0]+prev[1] = 1+2 = 3, prev[1]+prev[2] = 2+1 = 3. End with [1]. Row is [1,3,3,1].

Row 4: start with [1]. Inner: 1+3 = 4, 3+3 = 6, 3+1 = 4. End with [1]. Row is [1,4,6,4,1]. Final result: [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]. Notice the symmetry — each row reads the same forwards and backwards.

The edge cases are minimal. numRows = 1 returns [[1]]. numRows = 2 returns [[1], [1,1]]. Both are handled naturally by the base case and the loop — no special-casing needed. The constraint 1 <= numRows <= 30 means overflow is not a concern for standard integers.

The closely related problem is Pascal's Triangle II (#119), which asks for only a SINGLE specific row instead of all rows. This changes the space optimization strategy significantly. Instead of building all rows, you can generate the kth row in O(k) space by updating a single array in-place.

The key insight for #119 is to iterate from right to left when updating in-place. If you go left to right, you overwrite values you still need for the next computation. Going right to left ensures each prev[j-1] + prev[j] uses the original values. This in-place update pattern appears in many DP problems, including knapsack and coin change.

Pascal's Triangle is DP reduced to its essence. Every DP problem follows the same template: define subproblems, find the recurrence, determine the base case, and build up. In this problem, the subproblems are rows, the recurrence is prev[j-1] + prev[j], the base case is [1], and you build row by row. That is every DP problem in four steps.

The "build from previous result" pattern you see here is exactly what drives Climbing Stairs (#70), Unique Paths (#62), and every other linear DP problem. The only difference is that those problems hide the recurrence inside a word problem — Pascal's Triangle shows it to you directly. Master this problem and the DP mindset clicks.

If you want to solidify this pattern, practice generating Pascal's Triangle from memory, then move on to Climbing Stairs and Unique Paths. YeetCode flashcards can help you drill the recurrence relations until they are automatic — so when you see a new DP problem in an interview, you recognize the shape instead of starting from scratch.