Pascal's Triangle

Problem Statement

LeetCode-118: 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

Approach

Let’s try to understand the problem with an example. Consider the following Pascal’s triangle with 5 rows:

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

The first and last element of each row is always 1. The elements in between are the sum of the two elements directly above. We can use this property to generate the Pascal’s triangle.

The idea is to generate the Pascal’s triangle row by row. The first row is always [1]. For each subsequent row, we can generate the elements by summing the two elements directly above. The first and last element of each row is always 1.

Implementation

Here is a Java implementation of the approach:

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> result = new ArrayList<>();
    
    if(numRows == 0){
        return result;
    }
    
    result.add(List.of(1));
    
    for(int i=1; i<numRows; i++){
        List<Integer> row = new ArrayList<>();
        List<Integer> prevRow = result.get(i-1);
        
        row.add(1);
        
        for(int j=1; j<i; j++){
            row.add(prevRow.get(j-1) + prevRow.get(j));
        }
        
        row.add(1);
        result.add(row);
    }
    
    return result;
}

Complexity Analysis

The time complexity for the above approach is $O(n^2)$, where $n$ is the number of rows in Pascal’s triangle. The space complexity is $O(n^2)$ as well, as we are storing the entire Pascal’s triangle.