Problem Statement: Pascal’s Triangle
Pascal’s Triangle is a triangular array of binomial coefficients. Each row represents the coefficients of the binomial expansion for increasing powers of (x + y). The triangle starts with a 1 at the top (which is row 0), and each subsequent row contains the binomial coefficients for the expansion of (x + y)^n.
Example of Pascal’s Triangle:
Row 0: [1]
Row 1: [1, 1]
Row 2: [1, 2, 1]
Row 3: [1, 3, 3, 1]
Row 4: [1, 4, 6, 4, 1]
Row 5: [1, 5, 10, 10, 5, 1]
Task:
Given an integer numRows, generate the first numRows of Pascal’s Triangle.
Approach
- Properties of Pascal’s Triangle:
- The first and last element in any row is always
1. - The element at position
iin rowr(wherei > 0andi < r) is the sum of the two elements directly above it: Triangle[r][i]=Triangle[r−1][i−1]+Triangle[r−1][i]\text{Triangle}[r][i] = \text{Triangle}[r-1][i-1] + \text{Triangle}[r-1][i]Triangle[r][i]=Triangle[r−1][i−1]+Triangle[r−1][i]
- The first and last element in any row is always
- Algorithm:
- Initialize a list with one row
[1]. - For each row from 1 to
numRows - 1:- Start and end with
1. - Each middle element is the sum of the two elements directly above it (from the previous row).
- Start and end with
- Return the generated triangle.
- Initialize a list with one row
- Time Complexity:
- O(n^2), where
nis the number of rows. Each row containsielements, and the total number of operations is the sum of the firstnintegers, i.e.,O(n^2).
- O(n^2), where
- Space Complexity:
- O(n^2), since we store all the elements of the triangle.
Code Implementation in Multiple Languages
C:
#include <stdio.h>
void generate(int numRows) {
int triangle[numRows][numRows];
for (int i = 0; i < numRows; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i)
triangle[i][j] = 1;
else
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
}
// Print the triangle
for (int i = 0; i < numRows; i++) {
for (int j = 0; j <= i; j++) {
printf("%d ", triangle[i][j]);
}
printf("\n");
}
}
int main() {
int numRows = 5;
generate(numRows);
return 0;
}
C++:
#include <iostream>
#include <vector>
using namespace std;
void generate(int numRows) {
vector<vector<int>> triangle(numRows);
for (int i = 0; i < numRows; i++) {
triangle[i].resize(i + 1, 1); // Resize and fill with 1's
for (int j = 1; j < i; j++) {
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
}
// Print the triangle
for (const auto& row : triangle) {
for (int num : row) {
cout << num << " ";
}
cout << endl;
}
}
int main() {
int numRows = 5;
generate(numRows);
return 0;
}
Java:
import java.util.ArrayList;
import java.util.List;
public class PascalsTriangle {
public static List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
row.add(1); // First element of each row is 1
// Fill in the middle elements of the row
for (int j = 1; j < i; j++) {
row.add(triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j));
}
if (i > 0) {
row.add(1); // Last element of each row is 1
}
triangle.add(row);
}
return triangle;
}
public static void main(String[] args) {
int numRows = 5;
List<List<Integer>> result = generate(numRows);
// Print the triangle
for (List<Integer> row : result) {
for (int num : row) {
System.out.print(num + " ");
}
System.out.println();
}
}
}
Python:
def generate(numRows):
triangle = []
for i in range(numRows):
row = [1] * (i + 1) # Initialize a row with 1's
for j in range(1, i):
row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
triangle.append(row)
return triangle
# Example usage
numRows = 5
triangle = generate(numRows)
# Print the triangle
for row in triangle:
print(row)
C#:
using System;
using System.Collections.Generic;
class PascalsTriangle {
public static List<List<int>> Generate(int numRows) {
var triangle = new List<List<int>>();
for (int i = 0; i < numRows; i++) {
var row = new List<int>(new int[i + 1]);
row[0] = 1; // First element of each row is 1
row[i] = 1; // Last element of each row is 1
for (int j = 1; j < i; j++) {
row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
triangle.Add(row);
}
return triangle;
}
static void Main() {
int numRows = 5;
var triangle = Generate(numRows);
// Print the triangle
foreach (var row in triangle) {
foreach (var num in row) {
Console.Write(num + " ");
}
Console.WriteLine();
}
}
}
JavaScript:
function generate(numRows) {
let triangle = [];
for (let i = 0; i < numRows; i++) {
let row = Array(i + 1).fill(1); // Initialize a row with 1's
// Fill in the middle elements of the row
for (let j = 1; j < i; j++) {
row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
}
triangle.push(row);
}
return triangle;
}
// Example usage
let numRows = 5;
let triangle = generate(numRows);
// Print the triangle
triangle.forEach(row => {
console.log(row.join(' '));
});
Explanation of Output:
For numRows = 5, the generated Pascal’s Triangle will look like:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Each element is computed as the sum of the two elements directly above it. For instance, the element 3 in the 4th row is the sum of the two 3s from the 3rd row, and so on.
Summary:
- Pascal’s Triangle is a simple, yet powerful mathematical structure that can be efficiently generated using dynamic programming.
- The solutions provided implement the same approach across different languages, each maintaining the same time and space complexity of O(n²).