AlgoMaster Logo

Pascal's Triangle

Last Updated: March 31, 2026

easy

Understanding the Problem

We need to build Pascal's triangle row by row. Each row starts and ends with 1, and every element in between is the sum of the two elements directly above it from the previous row.

The structure is straightforward once you see it. Row 0 is just [1]. Row 1 is [1, 1]. For row 2, the edges are 1, and the middle element is 1 + 1 = 2, giving [1, 2, 1]. Row 3 takes the middle values from row 2: 1 + 2 = 3 and 2 + 1 = 3, producing [1, 3, 3, 1].

The key observation is that row i has exactly i + 1 elements, and element j in row i (where j is not the first or last) equals row[i-1][j-1] + row[i-1][j]. This dependency on the previous row is what drives the solution.

Key Constraints:

  • 1 <= numRows <= 30 → With numRows at most 30, the total number of elements is at most 465. Even an O(n^3) approach would be trivially fast. There is no performance pressure here.
  • The output is a 2D list of integers, so we need to build the triangle as a list of lists.
  • Values can get large but not overflow. The largest value in row 29 is C(29, 14) = 1,166,803,110, which fits in a 32-bit integer.

Approach 1: Iterative Row-by-Row Construction

Intuition

The most natural way to build Pascal's triangle is exactly how you'd draw it by hand. Start with the first row [1], then generate each subsequent row using the one before it.

For each new row, we know the first and last elements are always 1. For everything in the middle, we just look up at the previous row and add the two numbers that sit above and to the left. That's it. No fancy algorithms needed, just a nested loop.

Algorithm

  1. Initialize the result with the first row [[1]].
  2. For each row index i from 1 to numRows - 1:
    • Create a new row starting with [1].
    • For each position j from 1 to i - 1, compute the value as previousRow[j-1] + previousRow[j] and append it.
    • Append 1 at the end of the row.
    • Add the completed row to the result.
  3. Return the result.

Example Walkthrough

1Row 0: Base case, just [1]
0
1
1/6

Code

This approach is already optimal in terms of time complexity, since we must produce every element in the triangle. But there's an alternative way to compute each row using a mathematical formula, without referencing the previous row at all.

Approach 2: Mathematical (Combinatorial) Construction

Intuition

Every element in Pascal's triangle is a binomial coefficient. Specifically, element j in row i equals C(i, j) = i! / (j! * (i-j)!).

But computing factorials directly would be wasteful and risk overflow. There's a much cleaner trick. Once you know one element in a row, you can get the next one with a simple multiplication and division:

C(i, j) = C(i, j-1) * (i - j + 1) / j

So we can generate each row by starting with 1 (since C(i, 0) = 1) and then multiplying by a ratio to get the next element. No need to look at the previous row at all.

Algorithm

  1. Initialize the result list.
  2. For each row index i from 0 to numRows - 1:
    • Start the row with [1].
    • For each position j from 1 to i, compute the next value as previousValue * (i - j + 1) / j.
    • Add the completed row to the result.
  3. Return the result.

Example Walkthrough

1Row 0: C(0,0) = 1 → [1]
0
1
1/6

Code