LeetCode - Pascal's Triangle
Problem statement
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:
Problem statement taken from: https://leetcode.com/problems/pascals-triangle
Example 1:
Input: numRows = 5
Output: [ [1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1] ]
Example 2:
Input: numRows = 1
Output: [[1]]
Constraints:
- 1 <= numRows <= 30Explanation
Brute force approach
A simple method is to run two loops and calculate the value of Binominal Coefficient in the inner loop.
For example, the first line has 1, the second line has 1 1, the third line has 1 2 1,.. and so on. Every entry in a line is the value of a Binomial Coefficient. The value of the ith entry in line number line is C(line, i). The value can be calculated using the following formula.
C(line, i) = line! / ( (line-i)! * i! )A small C++ snippet of the above logic is:
void printPascal(int n)
{
for (int line = 0; line < n; line++){
for (int i = 0; i <= line; i++)
cout <<' '<< binomialCoefficient(line, i);
cout <<'\n';
}
}
int binomialCoefficient(int n, int k)
{
int result = 1;
if (k > n - k)
k = n - k;
for (int i = 0; i < k; ++i){
result *= (n - i);
result /= (i + 1);
}
return result;
}Since we are generating a coefficient for each iteration the time complexity of the above problem is O(N^3).
Optimized solution (O(N^2) time and O(N^2) extra space)
If we take a look at the Pascal triangle, we can see that every entry is the sum of the two values above it. So we created a 2D array that stores the previously generated values.
A small C++ snippet of the above logic is:
for (int line = 0; line < n; line++) {
for (int i = 0; i <= line; i++) {
if (line == i || i == 0)
arr[line][i] = 1;
else
arr[line][i] = arr[line - 1][i - 1] + arr[line - 1][i];
cout << arr[line][i] << ' ';
}
cout << '\n';
}Optimized solution (O(N^2) time and O(1) extra space)
This approach is based on the Brute force approach. The binomial coefficient of ith entry can be represented as C(line, i) and all lines start with value 1. The idea here is to calculate C(line, i) using C(line, i - 1). It can be calculated in O(1) time using the following.
C(line, i) = line! / ( (line - i)! * i! )
C(line, i - 1) = line! / ( (line - i + 1)! * (i - 1)! )
So using the above approach we can change the formula as below:
C(line, i) = C(line, i - 1) * (line - i + 1) / i
C(line, i) can be calculated from C(line, i - 1) in O(1) time.
Let's check the algorithm:
- initialize vector<vector<int>> result
- loop for line = 1; line <= n; line++
- initialize vector<int> temp
- set C = 1
- loop for i = 1; i <= line; i++
- temp.push_back(C)
- C = C * (line - i) / i
- result.push_back(temp)
- return result
C++ solution
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> result;
for (int line = 1; line <= numRows; line++){
vector<int> temp;
int C = 1;
for (int i = 1; i <= line; i++){
temp.push_back(C);
C = C * (line - i) / i;
}
result.push_back(temp);
}
return result;
}
};Golang solution
func generate(numRows int) [][]int {
var result [][]int
for line := 1; line <= numRows; line++ {
var temp []int
C := 1
for i := 1; i <= line; i++ {
temp = append(temp, C);
C = C * (line - i) / i;
}
result = append(result, temp)
}
return result
}Javascript solution
var generate = function(numRows) {
var result = [];
for(let line = 1; line <= numRows; line++){
var temp = [];
let C = 1;
for(let i = 1; i <= line; i++){
temp.push(C);
C = C * (line - i) / i;
}
result.push(temp);
}
return result;
};Dry Run
Let's dry-run our algorithm to see how the solution works.
Input: numRows = 3
Step 1: initialize vector<vector<int>> result
Step 2: loop for line = 1; line <= numRows
1 <= 3
true
initialize vector<int> temp
C = 1
loop for i = 1; i <= line
1 <= 1
true
temp.push_back(C);
temp = [1]
C = C * (line - i) / i;
C = 1 * (1 - 1) / 1
C = 0
i++
i = 2
loop for i <= line
2 <= 1
false
result.push_back(temp)
result = [[1]]
line++
line = 2
Step 3: loop for line <= numRows
2 <= 3
true
initialize vector<int> temp
C = 1
loop for i = 1; i <= line
1 <= 2
true
temp.push_back(C);
temp = [1]
C = C * (line - i) / i
C = 1 * (2 - 1) / 1
C = 1 * 1 / 1
i++
i = 2
loop for i <= line
2 <= 2
true
loop for i <= line
2 <= 2
true
temp.push_back(C);
temp = [1, 1]
C = C * (line - i) / i
C = 1 * (2 - 2) / 1
C = 1 * 0 / 1
C = 0
i++
i = 3
loop for i <= line
3 <= 2
false
result.push_back(temp)
result = [[1], [1, 1]]
line++
line = 3
Step 4: loop for line <= numRows
3 <= 3
true
initialize vector<int> temp
C = 1
loop for i = 1; i <= line
1 <= 3
true
temp.push_back(C);
temp = [1]
C = C * (line - i) / i
C = 1 * (3 - 1) / 1
C = 1 * 2 / 1
C = 2
i++
i = 2
loop for i <= line
2 <= 3
true
temp.push_back(C);
temp = [1, 2]
C = C * (line - i) / i
C = 2 * (3 - 2) / 2
C = 2 * 1 / 2
C = 1
i++
i = 3
loop for i <= line
3 <= 3
true
temp.push_back(C);
temp = [1, 2, 1]
C = C * (line - i) / i
C = 1 * (3 - 3) / 3
C = 1 * 0 / 3
C = 0
i++
i = 4
loop for i <= line
4 <= 3
false
result.push_back(temp)
result = [[1], [1, 1], [1, 2, 1]]
line++
line = 4
Step 5: loop for line <= numRows
4 <= 3
false
Step 6: return result
So the result is [[1], [1, 1], [1, 2, 1]].