Pascal's Triangle

Updated on 02 July, 2025
Pascal's Triangle header image

Problem Statement

Given a positive integer numRows, the task is to generate the first numRows rows of Pascal's Triangle and return them in a list of lists format. Pascal's Triangle is a triangular array of binomial coefficients. For a given number at row and column in this triangle, the value is the sum of the two directly adjacent numbers on the previous row. Specifically, the top of the triangle starts with a 1, and subsequent rows are constructed by adding the number above and to the left with the number above and to the right.

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]]

Constraints

  • 1 <= numRows <= 30

Approach and Intuition

To construct Pascal's Triangle up to a given number of rows, numRows, we can utilize a simple iterative approach based on the properties of the triangle:

  1. Initializing the Triangle: Start by initializing the triangle with the first row [[1]].
  2. Generating Subsequent Rows:
    • For each new row, start with a 1 because each row in Pascal's Triangle begins with this number.
    • Then, to generate the i-th element of a row, use the formula: sum of the (i-1)-th and i-th elements of the previous row. This comes from the triangle's property where each element is the sum of the two elements directly above it.
    • Each row ends with a 1, mirroring how it starts.
  3. Repeat until numRows: Continue adding rows until the triangle has numRows rows.

The example scenarios help illustrate this pattern:

  • Example 1: The user asks for numRows = 5. Starting from the initial [1], generate subsequent rows till the fifth row. The result for five rows, as seen, would be [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]], showcasing the construction of rows based on the sums of elements from preceding rows.

  • Example 2: When numRows = 1, the resulting Pascal's Triangle consists of just the first row, [[1]].

The constraints clarify that 1 <= numRows <= 30, ensuring the approach needs to handle creating up to thirty rows, which is computationally feasible with the outlined method.

Solutions

  • C++
  • Java
  • C
  • JavaScript
  • Python
cpp
class Solution {
public:
    vector<vector<int>> pascalTriangle(int rows) {
        vector<vector<int>> pTriangle;
        pTriangle.push_back({1});
        for (int i = 1; i < rows; i++) {
            vector<int> currentRow;
            vector<int> prevRow = pTriangle[i - 1];
            currentRow.push_back(1);
            for (int k = 1; k < i; k++) {
                currentRow.push_back(prevRow[k - 1] + prevRow[k]);
            }
            currentRow.push_back(1);
            pTriangle.push_back(currentRow);
        }
        return pTriangle;
    }
};

This summary provides a solution to generate Pascal's Triangle using C++.

  • The function pascalTriangle(int rows) is defined within a class called Solution.

  • The function takes an integer rows, which specifies the number of rows in Pascal's Triangle to be generated.

  • The function initializes a two-dimensional vector pTriangle to store the rows of the triangle.

  • Start by adding the first row [1] to pTriangle.

  • Iterate from 1 to rows - 1 to construct each row of the triangle:

    • Initialize an empty vector currentRow.
    • Retrieve the previous row from pTriangle and store it in prevRow.
    • Add the first element 1 to currentRow.
    • Use a for loop inside the iteration to calculate the values between the first and last element of each row:
      • Each middle element is the sum of two consecutive elements in prevRow.
    • Add the last element 1 to currentRow.
    • Append currentRow to pTriangle.
  • Finally, return pTriangle, which now contains all the rows of Pascal's Triangle up to the specified number of rows.

java
class Solution {
    public List<List<Integer>> pascalTriangle(int totalRows) {
        List<List<Integer>> pTriangle = new ArrayList<>();
    
        pTriangle.add(new ArrayList<>());
        pTriangle.get(0).add(1);
    
        for (int index = 1; index < totalRows; index++) {
            List<Integer> currentRow = new ArrayList<>();
            List<Integer> previousRow = pTriangle.get(index - 1);
    
            currentRow.add(1);
    
            for (int i = 1; i < index; i++) {
                currentRow.add(previousRow.get(i - 1) + previousRow.get(i));
            }
    
            currentRow.add(1);
            pTriangle.add(currentRow);
        }
    
        return pTriangle;
    }
}

The given Java program generates Pascal's Triangle with a specified number of rows, identified by the parameter totalRows. The method pascalTriangle(int totalRows) constructs a list of lists where each list represents a row in Pascal's Triangle.

  • Start by initializing pTriangle as an ArrayList of List of Integer.
  • Add the first row to pTriangle as it always consists of one element, the number 1.
  • Iterate from the second row until the total number of rows using a for loop. For each row:
    • Initialize currentRow as an ArrayList of Integer.
    • Reference previousRow from pTriangle based on the current index.
    • Add 1 to the beginning of currentRow for the edges of Pascal's Triangle.
    • Use a nested loop to calculate values between the edges of the triangle, summing the two adjacent numbers from previousRow.
    • Add 1 to the end of currentRow since the rightmost element in each row is also always 1.
    • Append currentRow to pTriangle.
  • Return the fully constructed pTriangle containing all rows of Pascal's Triangle up to totalRows.

This program efficiently builds each row based on the values of the previous row, demonstrating a classic use of dynamic programming to handle combinatorial number generation.

c
int** createPascalTriangle(int numLevels, int* levelsCount, int** levelSizes) {
    *levelsCount = numLevels;
    *levelSizes = (int*)malloc(sizeof(int) * numLevels);
    int** pascal = (int**)malloc(sizeof(int*) * numLevels);
    if (numLevels == 0) {
        return NULL;
    }
    (*levelSizes)[0] = 1;
    pascal[0] = (int*)malloc(sizeof(int) * 1);
    pascal[0][0] = 1;
    for (int i = 1; i < numLevels; i++) {
        int* currentLevel = (int*)malloc(sizeof(int) * (i + 1));
        int* previousLevel = pascal[i - 1];
        currentLevel[0] = 1;
        for (int k = 1; k < i; k++) {
            currentLevel[k] = previousLevel[k - 1] + previousLevel[k];
        }
        currentLevel[i] = 1;
        pascal[i] = currentLevel;
        (*levelSizes)[i] = i + 1;
    }
    return pascal;
}

The provided C program generates Pascal's Triangle, a triangular array of binomial coefficients, up to a specified number of levels given by numLevels. Each row of the triangle is constructed dynamically using memory allocation functions.

  • Initialize the triangle with a dynamically allocated memory for storing integer pointers (int** pascal) corresponding to each level.
  • A levels counter (levelsCount) and a size array (levelSizes) are allocated to record the number of integers in each level of the triangle.
  • The program begins by checking if the number of levels is zero and if so, returns NULL, indicating that no triangle is to be generated.
  • The first level of the triangle is initialized to [1].
  • Starting from the second level, each level is computed based on the values of the previous level:
    • The first and last item of every level are set to 1.
    • The intermediate values are calculated as the sum of two adjacent numbers from the previous level.
  • As each level is constructed, it's allocated dynamically and its size is recorded.

This structured approach ensures that even for a large number of levels, the Pascal Triangle is accurately constructed and memory is efficiently managed without any leaks, as each level's size is tracked separately allowing for precise memory allocation.

js
var buildPascalTriangle = function(totalRows) {
    const pascal = [];
    pascal.push([1]);
    for (let index = 1; index < totalRows; index++) {
        const currentRow = [];
        const lastRow = pascal[index - 1];
        currentRow.push(1);
        for (let j = 1; j < index; j++) {
            currentRow.push(lastRow[j - 1] + lastRow[j]);
        }
        currentRow.push(1);
        pascal.push(currentRow);
    }
    return pascal;
};

In the provided JavaScript solution, a function named buildPascalTriangle generates Pascal's Triangle up to a given number of rows (totalRows). This computation is achieved using arrays and nested loops, which systematically build each row based on the values from the previous row.

  • Initialize a main array pascal which will store each row of Pascal's Triangle.
  • Start by adding the first row manually, which is always [1].
  • Utilize a for-loop starting from index = 1 to less than totalRows. For each iteration:
    1. Create an array currentRow to store individual numbers for the current row.
    2. Retrieve the last row from pascal to calculate values for currentRow.
    3. Begin each currentRow with a 1 (as every row in Pascal's Triangle starts and ends with 1).
    4. Employ another nested loop which goes from j = 1 to less than index. In this loop:
    • Calculate the values by summing appropriate elements from lastRow and add those to currentRow.
    1. After the loop, push a 1 to currentRow to complete the row.
    2. Add currentRow to pascal.
  • Upon completion of the for-loop, return the pascal array which now contains all the computed rows of Pascal's Triangle.

By the end of this function call, a complete Pascal's Triangle of totalRows height is returned. The solution efficiently demonstrates using basic looping constructs and array manipulation to build a progressively increasing structure in a common mathematical model.

python
class Solution:
    def pascal_triangle(self, nrows: int) -> List[List[int]]:
        result = []
    
        for i in range(nrows):
            # Initialize all elements of this row as None
            row = [None] * (i + 1)
            row[0], row[-1] = 1, 1  # First and last elements are 1
    
            # Compute the values for the inner cells of this row
            for j in range(1, len(row) - 1):
                row[j] = result[i - 1][j - 1] + result[i - 1][j]
    
            result.append(row)
    
        return result

The provided Python function generates Pascal's Triangle up to a given number of rows. Pascal's Triangle is a geometric arrangement of binomial coefficients into a triangle, where each number is the sum of the two directly above it from the previous row.

  • The function pascal_triangle accepts an integer nrows, which specifies the number of rows of the triangle to generate.
  • The function initializes an empty list result to store each row of the triangle as a sublist.
  • A loop runs from 0 to nrows-1. For each iteration:
    • A new list row is created with size i+1, where all elements are initialized as None.
    • The first and the last element of row are set to 1.
    • For each position in the middle of the row, the value is calculated by the sum of two elements directly above it from the previous row in the triangle.
    • The fully formed row is then appended to the result list.
  • After completing all iterations, the function returns result, which contains the fully constructed Pascal's Triangle up to the desired number of rows.

This function efficiently builds Pascal's Triangle, ensuring that each element of each row is correctly calculated using dynamic programming principles.

Comments

No comments yet.