Description:
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:
Examples:
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]]Solution in Python:
To generate the first numRows of Pascal’s triangle in Python, we can follow a simple iterative approach. Pascal’s triangle is a triangular array of integers where the number at the position (i, j) is the sum of the numbers directly above it in the previous row (i-1, j-1) and (i-1, j).
Here is the detailed step-by-step solution:
- Initialization: Create an empty list to hold the rows of Pascal’s triangle.
- First Row: Add the first row, which is always
[1]. - Iterate to Build Each Row:
- For each subsequent row, start and end with
1. - Each element in the middle is the sum of the two elements directly above it from the previous row.
- For each subsequent row, start and end with
- Return the List of Rows: After building the required number of rows, return the list.
Python
from typing import List
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
# Initialize the list to hold the rows of Pascal's triangle
triangle = []
# Build each row
for row_num in range(numRows):
# Start with a row filled with 1s
row = [1] * (row_num + 1)
# Compute the values for the middle elements
for j in range(1, row_num):
row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j]
# Add the completed row to the triangle
triangle.append(row)
return triangle
# Example usage:
solution = Solution()
print(solution.generate(5)) # Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
print(solution.generate(1)) # Output: [[1]]Explanation:
- Imports: Import
Listfromtypingfor type hinting. - Class Definition: Define the
Solutionclass with thegeneratemethod. - Initialize Triangle: Start with an empty list
triangleto store the rows. - Outer Loop: Iterate from
0tonumRows - 1to build each row:- Create a new row filled with
1s of lengthrow_num + 1. - Inner Loop: For each position
jfrom1torow_num - 1, update the value by summing the two values directly above it from the previous row.
- Create a new row filled with
- Append Row: Add the completed row to the
triangle. - Return Triangle: Return the constructed list of rows.
Solution in Javascript:
JavaScript
/**
* @param {number} numRows
* @return {number[][]}
*/
var generate = function(numRows) {
// Initialize the list to hold the rows of Pascal's triangle
let triangle = [];
// Build each row
for (let rowNum = 0; rowNum < numRows; rowNum++) {
// Start with a row filled with 1s
let row = new Array(rowNum + 1).fill(1);
// Compute the values for the middle elements
for (let j = 1; j < rowNum; j++) {
row[j] = triangle[rowNum - 1][j - 1] + triangle[rowNum - 1][j];
}
// Add the completed row to the triangle
triangle.push(row);
}
return triangle;
};
// Example usage:
console.log(generate(5)); // Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
console.log(generate(1)); // Output: [[1]]Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> generate(int numRows) {
// Initialize the list to hold the rows of Pascal's triangle
List<List<Integer>> triangle = new ArrayList<>();
// Build each row
for (int rowNum = 0; rowNum < numRows; rowNum++) {
// Initialize the current row with 1s
List<Integer> row = new ArrayList<>();
for (int i = 0; i <= rowNum; i++) {
row.add(1);
}
// Compute the values for the middle elements
for (int j = 1; j < rowNum; j++) {
int sum = triangle.get(rowNum - 1).get(j - 1) + triangle.get(rowNum - 1).get(j);
row.set(j, sum);
}
// Add the completed row to the triangle
triangle.add(row);
}
return triangle;
}
// Main method for testing
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.generate(5)); // Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
System.out.println(solution.generate(1)); // Output: [[1]]
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> Generate(int numRows) {
// Initialize the list to hold the rows of Pascal's triangle
IList<IList<int>> triangle = new List<IList<int>>();
// Build each row
for (int rowNum = 0; rowNum < numRows; rowNum++) {
// Initialize the current row with 1s
List<int> row = new List<int>(new int[rowNum + 1]);
row[0] = 1;
row[rowNum] = 1;
// Compute the values for the middle elements
for (int j = 1; j < rowNum; j++) {
int sum = triangle[rowNum - 1][j - 1] + triangle[rowNum - 1][j];
row[j] = sum;
}
// Add the completed row to the triangle
triangle.Add(row);
}
return triangle;
}
}