118. Pascal’s Triangle

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

 

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

From: LeetCode
Link: 118. Pascal’s Triangle

---

Solution:

Ideas：

1. Memory Allocation for the Triangle:
The function starts by allocating memory for an array of integer pointers, triangle, which will store the rows of Pascal’s Triangle. The size of this array is numRows, each element of which will be a pointer to an array representing a row in the triangle.

2. Memory Allocation for Column Sizes:
It also allocates memory for an array returnColumnSizes that holds the size of each row. This is needed because each row of Pascal’s Triangle has a different number of elements. For row i, there will be i + 1 elements.

3. Filling the Triangle:
The function then iterates over each row with two nested loops:

• The outer loop runs from 0 to numRows - 1, setting up each row.
• The inner loop runs through each row and calculates the value of each element based on the values from the previous row. The first and last elements of each row are always 1.

4. First and Last Elements:
Within each row, before entering the inner loop, the first element is set to 1. After the inner loop, the last element is also set to 1.

5. Summation Rule:
The key operation occurs inside the inner loop, where each element is the sum of the two elements directly above it from the previous row: triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j]. This is the summation rule that defines Pascal’s Triangle.

6. Return Values:
Finally, the function sets the returnSize to the number of rows (numRows) to indicate how many rows are in the returned triangle and returns the pointer to the array of arrays, which is Pascal’s Triangle.

Code:

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** generate(int numRows, int* returnSize, int** returnColumnSizes) {
    // Allocate memory for the array of arrays
    int** triangle = (int**)malloc(numRows * sizeof(int*));
    *returnColumnSizes = (int*)malloc(numRows * sizeof(int));

    for (int i = 0; i < numRows; i++) {
        // Set the return size for each row
        (*returnColumnSizes)[i] = i + 1;

        // Allocate memory for each row
        triangle[i] = (int*)malloc((*returnColumnSizes)[i] * sizeof(int));
        triangle[i][0] = 1; // first element is always 1

        // Set the elements of the triangle
        for (int j = 1; j < i; j++) {
            // Each element equals the sum of the elements above it
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }

        triangle[i][i] = 1; // last element is always 1
    }

    // Set the return size
    *returnSize = numRows;
    
    return triangle;
}