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

Solution Approach

Generate Pascal's triangle up to numRows. Each row starts and ends with 1. Every interior element is the sum of the two elements directly above it from the previous row: triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j].

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

Initialize each row with 1s, then fill the interior using values from the previous row. The first two rows are [1] and [1,1] which serve as base cases. Each subsequent row has one more element than the previous.

Time complexity is O(numRows^2), space complexity is O(numRows^2) for the output.

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;
    }
}