118. Pascal’s Triangle Leetcode Solution
Pascal’s Triangle Leetcode Problem :
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.
Pascal’s Triangle Leetcode Solution :
Constraints :
- 1 <= numRows <= 30
Example 1:
- Input: numRows = 1
- Output: [[1]]
Intuition :
The problem is asking to generate the first numRows of Pascal’s triangle. Pascal’s triangle is a mathematical construct where each number is the sum of the two numbers directly above it. It is often used in combinatorics and probability theory. The intuition here is to build Pascal’s triangle row by row, starting with the initial row and calculating subsequent rows based on the values of the previous row.
Approach :
The approach is to iterate through each row of Pascal’s triangle, starting with the first row. For each subsequent row, we calculate the values by summing the corresponding elements from the previous row. The outer loop iterates through each row, and the inner loop calculates the values for each element in the current row (except the first and last, which are always 1). We then append each row to the result, gradually building Pascal’s triangle.The approach is to iterate through each row of Pascal’s triangle, starting with the first row. For each subsequent row, we calculate the values by summing the corresponding elements from the previous row. The outer loop iterates through each row, and the inner loop calculates the values for each element in the current row (except the first and last, which are always 1). We then append each row to the result, gradually building Pascal’s triangle.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
vector< vector< int>> generate(int numRows) {
if (numRows == 0) return {};
if (numRows == 1) return {{1}};
vector< vector< int>> prevRows = generate(numRows - 1);
vector< int> newRow(numRows, 1);
for (int i = 1; i < numRows - 1; i++) {
newRow[i] = prevRows.back()[i - 1] + prevRows.back()[i];
}
prevRows.push_back(newRow);
return prevRows;
}
};
class Solution {
public List< List< Integer>> generate(int numRows) {
if (numRows == 0) return new ArrayList<>();
if (numRows == 1) {
List< List< Integer>> result = new ArrayList<>();
result.add(Arrays.asList(1));
return result;
}
List< List< Integer>> prevRows = generate(numRows - 1);
List< Integer> newRow = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
newRow.add(1);
}
for (int i = 1; i < numRows - 1; i++) {
newRow.set(i, prevRows.get(numRows - 2).get(i - 1) + prevRows.get(numRows - 2).get(i));
}
prevRows.add(newRow);
return prevRows;
}
}
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if numRows == 0:
return []
pascal = [[1]]
for i in range(1, numRows):
prev_row = pascal[i-1] # Get the previous row
current_row = [1] # The first element of each row is always 1
for j in range(1, i):
current_row.append(prev_row[j-1] + prev_row[j])
current_row.append(1) # The last element of each row is always 1
pascal.append(current_row) # Add the current row to Pascal's triangle
return pascal
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment