easy

Pascal's Triangle

Build the first few rows of Pascal's triangle.

1. Define the problem

Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal's triangle . In Pascal's triangle, each row starts and ends with 1, and every other number is the sum of the two numbers above it in the previous row. Build each row from the previous row instead of recomputing sums from scratch.

Constraints

  • 1 ≤ numRows ≤ 30

Example

InputnumRows = 5
Output[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

Explanation Each inner value is the sum of the two values above it in the previous row, for example 1+2=3, 2+1=3, and so on.

2. Know the words first

In plain terms

Pascal's triangle
A triangular arrangement of numbers where each row is built from the row above it, commonly used to show combinations and binomial coefficients.
3. Visualize the solution

The row is the newest triangle row, kept at its widest size with blanks

The row is the newest triangle row, kept at its widest size with blanks
Statusinit

Row 0 is always [1]. Only the first slot is in use, so the other three stay blank.

What happens in this step

row 0 = [1]
result = [[1]]
Step 1 of 4

Steps to visualize

  1. The row below always has four slots, because the last row we build is four numbers wide.
  2. A slot showing — is not part of the triangle row yet.
  3. Start with the first row, which is just [1].
  4. For each new row, start and end it with 1, and fill every middle slot with the sum of the two values above it.
  5. The highlight box covers the slots the current row is using.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the newest triangle row, kept at its widest size with blanks
Statusinit

Row 0 is always [1]. Only the first slot is in use, so the other three stay blank.

What happens in this step

row 0 = [1]
result = [[1]]
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function generate(numRows) {
  const result = [[1]];

  for (let r = 1; r < numRows; r++) {
    const previous = result[r - 1];
    const row = [1];

    for (let i = 1; i < r; i++) {
      row.push(previous[i - 1] + previous[i]);
    }

    row.push(1);
    result.push(row);
  }

  return result;
}
Time
O(numRows^2)
Space
O(numRows^2)
6. Test cases

Test cases

InputExpectedCovers
numRows = 5[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]example from the docstring
numRows = 1[[1]]smallest valid input, a single row
numRows = 2[[1], [1, 1]]boundary case, exactly two rows
numRows = 3[[1], [1, 1], [1, 2, 1]]smallest case with a computed middle value
numRows = 6[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]larger triangle with multiple computed middle values

Keep reading