Leetcode 118. Pascal's Triangle

Problem

In this problem, we are required to create the first 'numRows' of Pascal's triangle, given a non-negative integer 'numRows'. The Pascal's triangle is a triangular array of the binomial coefficients, where each number is the sum of the two numbers directly above it.

For example, if we input 5, the output would be:

[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

Approach

The main pattern we need to recognize to approach this problem is in the values of the Pascal's triangle. Each row of the Pascal's triangle starts and ends with 1. The internal values of each row are obtained by summing the numbers that are at the same index and the one at the preceding index from the previous row.

Our approach is to create a 2-dimensional vector with the first 'numRows' rows, filled with 1s right away. After the initial filling, we calculate the internal values for each row (except the first two rows), which are sums of the numbers that are at the same index and the one at the preceding index from the previous row.

Walkthrough

To illustrate the approach, consider numRows=4, then the initial state of 2d vector is:

1
2
3[
4 [1],
5 [1,1],
6 [1,1,1],
7 [1,1,1,1]
8]

After that, we iterate from the third row and calculate internal values. We calculate the sum of the numbers at the same index and the preceding index from the previous row, as we can see with the below steps:

1
2
3[
4 [1],
5 [1,1],
6 [1,2,1], // 2=1(previous row's second index) + 1(previous row's first index)
7 [1,1,1,1]
8]

The process repeated for the 4th row:

1
2
3[
4 [1],
5 [1,1],
6 [1,2,1],
7 [1,3,3,1] // 3=1(previous row's second index) + 2(previous row's first index)
8           // 3=2(previous row's third index) + 1(previous row's second index)
9]
1
2
3# C++ solution
4

cpp class Solution { public: vector<vector> generate(int numRows) { vector<vector> ans;

1    for (int i = 0; i < numRows; ++i)
2        ans.push_back(vector<int>(i + 1, 1));
3
4    for (int i = 2; i < numRows; ++i)
5        for (int j = 1; j < ans[i].size() - 1; ++j)
6            ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];
7
8    return ans;
9}

};

1
2
3For each row, it creates a sub-vector of length 'i+1' (to accommodate 'i+1' elements in the row) and then fills it with 1s. Then it calculates the internal values for rows beginning from the third row, by adding the previous two numbers.
4
5# Java Solution
6

java class Solution { public List<List> generate(int numRows) { List<List> result = new ArrayList<>();

1    for(int i=0; i<numRows; i++) {
2        List<Integer> row = new ArrayList<>(Collections.nCopies(i+1, 1));
3        for(int j=1; j<i; j++) {
4            row.set(j, result.get(i-1).get(j-1)+result.get(i-1).get(j));
5        }
6        result.add(row);
7    }
8
9    return result;
10}

}

1
2
3
4# Python Solution
5

python class Solution: def generate(self, numRows): result = [[1]*i for i in range(1, numRows+1)] for i in range(2, numRows): for j in range(1, i): result[i][j] = result[i-1][j-1] + result[i-1][j] return result

1
2
3
4# JavaScript Solution
5

javascript var generate = function(numRows) { let result = [];

1for(let i=0; i<numRows; i++) {
2    result[i] = [];
3    result[i][0] = 1;
4    for(let j=1; j<i; j++) {
5        result[i][j] = result[i-1][j-1] + result[i-1][j];
6    }
7    result[i][i] = 1;
8}
9
10return result;

};

1
2In the Java, Python, and JavaScript solutions, we first create a nested list (2-dimensional array or list of lists) with numRows rows. We then fill every row with 1, this will serve as the solution to all boundary conditions for Pascal’s triangle (where j=0 or j=i).
3
4Then, for rows 2 to numRows (0-indexed), we compute every non-boundary element in the current row (col) as the sum of the two elements directly above it in the previous row (col-1, col), exactly as explained in the problem statement. This can be done inline and will result in the right answer due to the well-defined element-adding order.
5
6These solutions essentially follow the same approach but in different programming languages, and their time and space complexity is O(numRows^2) due to the usage of a numRows-by-numRows 2D array.
7
8The central concept in these solutions is Dynamic Programming, where we solve the problem by breaking it down into simpler, smaller sub-problems and using the answers to those sub-problems to construct an answer to the original problem. In the context of the Pascal Triangle problem, the sub-problems involve computing the values of each row based on the values from the row above, and the final problem solution is derived from the computed sub-problem solutions.

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫