1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/**
 * Iterative Row-by-Row Construction
 * Time Complexity: O(n²) - We generate n rows with a total of n(n+1)/2 elements
 * Space Complexity: O(n²) - We store all elements of the triangle
 * 
 * @param {number} numRows - Number of rows to generate
 * @return {number[][]} - Pascal's Triangle with numRows rows
 */
function generate(numRows) {
  // Initialize result with the first row
  const result = [[1]];
  
  // Generate each row based on the previous row
  for (let i = 1; i < numRows; i++) {
    // Start with 1
    const row = [1];
    
    // Calculate middle elements
    for (let j = 1; j < i; j++) {
      row.push(result[i - 1][j - 1] + result[i - 1][j]);
    }
    
    // End with 1
    row.push(1);
    
    // Add row to result
    result.push(row);
  }
  
  return result;
}
 
/**
 * Mathematical Formula (Binomial Coefficients)
 * Time Complexity: O(n²) - We still generate n rows with a total of n(n+1)/2 elements
 * Space Complexity: O(n²) - We store all elements of the triangle
 * 
 * @param {number} numRows - Number of rows to generate
 * @return {number[][]} - Pascal's Triangle with numRows rows
 */
function generateMathematical(numRows) {
  const result = [];
  
  for (let i = 0; i < numRows; i++) {
    const row = [];
    
    // First element is always 1
    let value = 1;
    row.push(value);
    
    // Calculate remaining elements using the formula
    for (let j = 1; j <= i; j++) {
      value = value * (i - j + 1) / j;
      row.push(value);
    }
    
    result.push(row);
  }
  
  return result;
}
 
/**
 * Dynamic Programming Approach
 * Time Complexity: O(n²) - We fill a triangular portion of a 2D array
 * Space Complexity: O(n²) - We use a 2D array of size numRows × numRows
 * 
 * @param {number} numRows - Number of rows to generate
 * @return {number[][]} - Pascal's Triangle with numRows rows
 */
function generateDP(numRows) {
  // Initialize DP array
  const dp = Array(numRows).fill().map(() => Array(numRows).fill(0));
  
  // Base case
  dp[0][0] = 1;
  
  // Fill the DP array
  for (let i = 1; i < numRows; i++) {
    dp[i][0] = 1;  // First element
    dp[i][i] = 1;  // Last element
    
    for (let j = 1; j < i; j++) {
      dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    }
  }
  
  // Convert to result format
  const result = [];
  for (let i = 0; i < numRows; i++) {
    const row = [];
    for (let j = 0; j <= i; j++) {
      row.push(dp[i][j]);
    }
    result.push(row);
  }
  
  return result;
}
 
// Test cases
console.log(generate(5));
// [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
 
console.log(generate(1));
// [[1]]