Pascal's Triangle Leetcode
Asked 3 months ago
0Comments
0 Views
Pascal's Triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. Here's how we can approach this problem:
- We'll create a 2D vector to store the triangle.
- The first row always contains just one element: 1.
- For each subsequent row:
- The first and last elements are always 1.
- The middle elements are the sum of the two numbers directly above it in the previous row.
Let's implement this solution:
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> triangle;
// Handle edge case
if (numRows == 0) return triangle;
// First row is always [1]
triangle.push_back({1});
for (int i = 1; i < numRows; i++) {
vector<int> row;
vector<int>& prevRow = triangle[i-1];
// First element of the row is always 1
row.push_back(1);
// Calculate middle elements
for (int j = 1; j < i; j++) {
row.push_back(prevRow[j-1] + prevRow[j]);
}
// Last element of the row is always 1
row.push_back(1);
triangle.push_back(row);
}
return triangle;
}
};
Now, let me explain the code and the approach:
- We start by creating a 2D vector called
triangle
to store our result. - We handle the edge case where
numRows
is 0 by returning an empty triangle. - We always add the first row, which is just
[1]
. - Then, we iterate from the second row (index 1) up to the
numRows
-th row:- We create a new vector
row
for each row. - We add 1 as the first element of each row.
- For the middle elements, we sum the two numbers from the previous row.
- We add 1 as the last element of each row.
- Finally, we add the completed row to our triangle.
- We create a new vector
- After generating all rows, we return the triangle.
This solution has a time complexity of O(numRows^2) because we're iterating through each element of the triangle. The space complexity is also O(numRows^2) to store the entire triangle.
Share