#118 Pascal's Triangle - Solution

The Pascal's Triangle problem asks you to generate the first numRows of the triangle where each element is the sum of the two numbers directly above it. A common and efficient approach uses dynamic programming with an array (or list of lists). Start by initializing the first row with [1]. For each new row, set the first and last elements to 1, then compute the middle elements using values from the previous row.

This approach builds the triangle row by row, reusing previously computed values. Each element depends only on two elements from the previous row, making it a natural fit for dynamic programming. The overall time complexity grows with the number of elements generated across all rows, while the space complexity depends on storing the triangle structure.

By iterating through rows and constructing each using previously calculated values, the solution remains simple, readable, and efficient for interview settings.

Approach	Time Complexity	Space Complexity
Dynamic Programming (Build Row by Row)	O(n²)	O(n²)

Solutions (12)

Iterative Construction Approach

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.

C C++Java Python C#JavaScript

1#include <stdio.h>
2#include <stdlib.h>
3
4int** generate(int numRows, int* returnSize, int** returnColumnSizes)

Explanation

In this C implementation, we allocate a 2D array to hold the triangle's content. We initialize the first and last entries of each row to 1. For each intermediate row entry, we compute its value as the sum of the two appropriate values from the preceding row, incrementally building each row from top to bottom.

Recursive Pascal's Triangle Construction

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.

C C++Java Python C#JavaScript

1using System;
using System.Collections.Generic;

public class PascalTriangleRecursive {
    public static int Combination(int n, int k) {
        if (k == 0 || k == n) return 1;
        return Combination(n - 1, k - 1) + Combination(n - 1, k);
    }

    public static List<List<int>> Generate(int numRows) {
        List<List<int>> triangle = new List<List<int>>();
        for (int i = 0; i < numRows; i++) {
            List<int> row = new List<int>();
            for (int j = 0; j <= i; j++) {
                row.Add(Combination(i, j));
            }
            triangle.Add(row);
        }
        return triangle;
    }

    public static void Main(string[] args) {
        int numRows = 5;
        List<List<int>> result = Generate(numRows);
        foreach (var row in result) {
            Console.WriteLine(string.Join(" ", row));
        }
    }
}