118. Pascal's Triangle

Description

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

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

 

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]]

 

Constraints:

• 1 <= numRows <= 30

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n²)
• Space complexity: O(n²)

 

JavaScript

/**
 * @param {number} numRows
 * @return {number[][]}
 */
const generate = function (numRows) {
  const result = [[1]];

  for (let row = 2; row <= numRows; row++) {
    const prev = result.at(-1);
    const values = [1];

    for (let index = 1; index < prev.length; index++) {
      values.push(prev[index] + prev[index - 1]);
    }

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

  return result;
};