Sponsored
Sponsored
This approach involves generating Pascal's Triangle row by row using an iterative method. The first row is initialized with [1], and for each subsequent row, the first and last element are always 1. The intermediate elements are calculated as sums of appropriate elements from the previous row.
Time Complexity: O(numRows^2) due to the nested loop structure.
Space Complexity: O(numRows^2) as we store all elements of the triangle.
1import java.util.ArrayList;
2import java.util.List;
3
4public class PascalTriangle {
5 public static List<List<Integer>> generate(int numRows) {
6 List<List<Integer>> triangle = new ArrayList<>();
7 for (int i = 0; i < numRows; i++) {
8 List<Integer> row = new ArrayList<>();
9 row.add(1);
10 for (int j = 1; j < i; j++) {
11 List<Integer> prevRow = triangle.get(i - 1);
12 row.add(prevRow.get(j - 1) + prevRow.get(j));
13 }
14 if (i > 0) row.add(1);
15 triangle.add(row);
16 }
17 return triangle;
18 }
19
20 public static void main(String[] args) {
21 int numRows = 5;
22 List<List<Integer>> result = generate(numRows);
23 for (List<Integer> row : result) {
24 System.out.println(row);
25 }
26 }
27}
28In this Java implementation, we use the ArrayList class to keep track of Pascal's Triangle. By iteratively generating each row, referencing the prior row to compute new values, we dynamically adjust ArrayLists to store required values per row.
This approach constructs Pascal's Triangle using recursion by calculating each value based on the combination formula. The values on the edges are always 1, and other values are calculated as combinatorial numbers derived recursively.
Time Complexity: O(numRows^3) due to recursive calls, not optimal.
Space Complexity: O(numRows^2) for storing the triangle.
1#include <iostream>
#include <vector>
int combination(int n, int k) {
if (k == 0 || k == n) return 1;
return combination(n - 1, k - 1) + combination(n - 1, k);
}
std::vector<std::vector<int>> generate(int numRows) {
std::vector<std::vector<int>> triangle(numRows);
for (int i = 0; i < numRows; i++) {
triangle[i] = std::vector<int>(i + 1);
for (int j = 0; j <= i; j++) {
triangle[i][j] = combination(i, j);
}
}
return triangle;
}
int main() {
int numRows = 5;
std::vector<std::vector<int>> result = generate(numRows);
for (const auto& row : result) {
for (int value : row) {
std::cout << value << " ";
}
std::cout << std::endl;
}
return 0;
}
This C++ approach defines a recursive function that calculates each entry according to Pascal's combination principles. Recursive function calls compute combination values used in constructing each row incrementally.