Pascal's Triangle

Easyarraydynamic-programming
Category: Fundamentals
Companies that ask this question:
AmazonGoogleApple
LeetCode →

Approach

Pascal's Triangle

Approach

Build each row using values from previous row.

Algorithm

  1. Start with first row [1]
  2. For each subsequent row:
    • Start with 1
    • Each middle value = sum of two values above
    • End with 1
  3. Return complete triangle

Complexity

  • Time: O(n²) - generate all rows
  • Space: O(n²) - triangle storage

Key Insights

  • Each row has i+1 elements (0-indexed)
  • Each element = sum of two elements in previous row
  • Classic dynamic programming pattern

Solution

java
1class Solution {
2    public List<List<Integer>> generate(int numRows) {
3        List<List<Integer>> triangle = new ArrayList<>();
4        if (numRows == 0) return triangle;
5        
6        triangle.add(new ArrayList<>());
7        triangle.get(0).add(1);
8        
9        for (int i = 1; i < numRows; i++) {
10            List<Integer> row = new ArrayList<>();
11            List<Integer> prevRow = triangle.get(i - 1);
12            
13            row.add(1);
14            
15            for (int j = 1; j < i; j++) {
16                row.add(prevRow.get(j - 1) + prevRow.get(j));
17            }
18            
19            row.add(1);
20            triangle.add(row);
21        }
22        
23        return triangle;
24    }
25}
Loading visualizer...