How do you approach Pascal's Triangle?

Each row depends only on the row immediately above it, so build them in order and keep the previous row to hand.

What is the time complexity of Pascal's Triangle?

Time complexity: O(numRows^2) - the total number of entries.. Space complexity: O(numRows^2) for the output..

What are common mistakes on Pascal's Triangle?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Pascal's Triangle

EasyAlgorithms

Description

Given an integer numRows, return the first numRows of Pascal's triangle.

Each row starts and ends with 1, and every other entry is the sum of the two entries directly above it.

Example 1

Input: numRows = 5

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

Example 2

Input: numRows = 1

Output: [[1]]

Example 3

Input: numRows = 2

Output: [[1],[1,1]]

Constraints

- 1 <= numRows <= 30

Pascal's Triangle: approach, complexity and pitfalls

An easy dynamic programming problem, graded against 6 test cases (3 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 3-step hint ladder

Each row depends only on the row immediately above it, so build them in order and keep the previous row to hand.
Row i has i + 1 entries. The first and last are always 1.
For the interior positions, entry j is previous[j - 1] + previous[j].

The optimal approach

Show the approach: The simplest possible dynamic programming

Every entry is defined by entries already computed, and each row depends only on the row above it. That is dynamic programming in its most stripped-down form: a recurrence, evaluated bottom-up, with no memoization table beyond what you are already building.

Build row by row. Row `i` has `i + 1` entries; the ends are `1`, and interior entry `j` is `previous[j - 1] + previous[j]`. Because you always have the previous row in hand, no recursion or lookup structure is needed.

It is worth recognizing what the triangle contains, since interviewers often follow up: row `n` holds the binomial coefficients C(n, k), so entry (n, k) is also the number of ways to choose k items from n. That gives an O(k) direct formula for a single entry using the multiplicative identity - the right answer when asked for one row rather than all of them, which is a genuinely different problem ("Pascal's Triangle II") solvable in O(k) space.

The values grow quickly - row 30 already exceeds 10^8 - which is why the constraint stops there.

Time: O(numRows^2) - the total number of entries.
Space: O(numRows^2) for the output.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.