Code Logo

Pascal's Triangle

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given an integer numRows, generate the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it. The first and last elements of each row are always 1. This is a classic 2D dynamic programming problem where each cell depends on two cells from the previous row.

The triangle is built row by row. Start with the first row [1]. For each subsequent row, create an array of length i+1. Set the first and last elements to 1. For each inner position j, compute dp[i][j] = dp[i-1][j-1] + dp[i-1][j]. This recurrence expresses how values propagate through the triangle.

Pascal's triangle has many mathematical properties. It appears in binomial expansions, combinatorics (n choose k), and probability theory. The DP construction efficiently generates it in O(numRows²) time with O(numRows²) space for the output.

Edge cases include numRows = 0 (return empty list), numRows = 1 (return [[1]]), and numRows = 2 (return [[1],[1,1]]).

Pascal's triangle is the 2D DP foundation for combinatorial problems. Each value represents n-choose-k (binomial coefficient), making it useful for probability and counting. The triangle can also be computed row by row without storing the entire result using O(n) space.

Example Input & Output

Example 1
Input
2
Output
[[1],[1,1]]
Explanation

First two rows.

Example 2
Input
1
Output
[[1]]
Explanation

Single row.

Example 3
Input
3
Output
[[1],[1,1],[1,2,1]]
Explanation

Three rows.

Example 4
Input
5
Output
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Explanation

Five rows of Pascal's triangle.

Example 5
Input
0
Output
[]
Explanation

No rows.

Algorithm Flow

Recommendation Algorithm Flow for Pascal's Triangle
Recommendation Algorithm Flow for Pascal's Triangle

Solution Approach

Initialize with first row [1]. For each new row, set ends to 1, middle to sum of two above.

function solution(numRows) {
  var result = [];
  for (var i = 0; i < numRows; i++) {
    var row = [];
    for (var j = 0; j <= i; j++) {
      if (j === 0 || j === i) row.push(1);
      else row.push(result[i-1][j-1] + result[i-1][j]);
    }
    result.push(row);
  }
  return result;
}

Time O(n²), Space O(n²).

Best Answers

java
import java.util.*;
class Solution {
    public List<List<Integer>> solution(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) row.add(1);
                else row.add(result.get(i-1).get(j-1) + result.get(i-1).get(j));
            }
            result.add(row);
        }
        return result;
    }
}