Explorer
Data Structures & Algorithms

Generate Pascal's Triangle up to numRows.

Problem Statement

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.

Examples

Input: numRows = 5

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

Explanation: Combining the input according to Pascal's Triangle I logic yields [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]].

Input: numRows = 1

Output: [[1]]

Explanation: Combining the input according to Pascal's Triangle I logic yields [[1]].

Complexity

Time Complexity: O(N²)

Space Complexity: O(N²)

Hints

💡 Hint 1: Each row i has i + 1 elements, with row[0] = 1 and row[i] = 1. 💡 Hint 2: For any middle element row[j], its value is the sum of the two elements above it: result[i - 1][j - 1] + result[i - 1][j]. 💡 Hint 3: Build row by row from row 0 to numRows - 1.

Editorial & Approach

Problem Overview & Intuition

Every row starts and ends with 1. Each intermediate cell at row i and column j is the sum of result[i - 1][j - 1] and result[i - 1][j]. Building iteratively row by row takes O(numRows²).

Step-by-Step Approach

  1. Initialize result = [].
  2. Loop i from 0 to numRows - 1.
  3. Construct a new row of size i + 1 filled with 1.
  4. For j from 1 to i - 1: set row[j] = result[i - 1][j - 1] + result[i - 1][j].
  5. Append row to result.
  6. Return result.

Optimal Implementation (JavaScript)

function generatePascalsTriangle(numRows) {
  const result = [];
  for (let i = 0; i < numRows; i++) {
    const row = new Array(i + 1).fill(1);
    for (let j = 1; j < i; j++) {
      row[j] = result[i - 1][j - 1] + result[i - 1][j];
    }
    result.push(row);
  }
  return result;
}

Complexity Analysis

Time Complexity O(numRows²) — total entries computed is numRows * (numRows + 1) / 2.
Space Complexity O(numRows²) — memory for the output triangle.

Edge Cases & Corner Traps Handled

  • numRows = 1: returns [[1]].
  • numRows = 2: returns [[1], [1, 1]].

Pascal's Triangle I

Hard
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.
Example Scenarios
1Example 1
Input: numRows = 5
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Explanation:

Combining the input according to Pascal's Triangle I logic yields [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]].

2Example 2
Input: numRows = 1
Output: [[1]]
Explanation:

Combining the input according to Pascal's Triangle I logic yields [[1]].

Editor
Loading Editor...
numRows =
5
Output:Click "Run" above to execute and verify your code here.
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]