Algorithm Day83 - Pascal's Triangle

Posted on In , Views:

🧩 Problem 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:

1
2
3
4
5
    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

💬 Examples

Example 1

1
2
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2

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

💡 Intuition

Each row starts and ends with 1. For intermediate elements, the value equals the sum of the two elements above it from the previous row. We can build rows iteratively from top to bottom.

🔢 Java Code (Iterative)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = 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 {
                    List<Integer> prev = res.get(i - 1);
                    row.add(prev.get(j - 1) + prev.get(j));
                }
            }
            res.add(row);
        }
        return res;
    }
}

⏱ Complexity Analysis

  • Time: O(numRows^2) — we fill each entry of the triangle once.
  • Space: O(numRows^2) — output size.

✍️ Summary

  • Build each row using the previous row’s values.
  • Simple, iterative approach works efficiently for the problem constraints.

Related problems

  • lc-119 — Pascal’s Triangle II (specific row)
  • lc-118 variations involving combinatorics