Problem¶

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|1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Solve¶

O(n ** 2)

Simply simulating what the problem said, no optimizing anything

Time Submitted	Status	Runtime	Memory	Language
07/10/2023 23:40	Accepted	49 ms	16.2 MB	python3

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        answer = [[1], [1,1], [1,2,1|1], [1,1], [1,2,1]]

        for row in range(3,numRows):
            last = answer[row-1]
            current_row = [1]
            for index in range(len(last)-1):
                current_row.append(last[index] + last[index+1])

            current_row.append(1)
            answer.append(current_row)

        return answer[:numRows]

C Implementation¶

O(n ** 2)

Ton of pointer, hate to say that it is unclear which/how variable should be return back to Leetcode. For normal competition, result should be return through stdout or output file

Time Submitted	Status	Runtime	Memory	Language
09/09/2023 00:42	Accepted	7 ms	6.5 MB	c

/**

 * 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){
    int *s;
    int **res = malloc (sizeof (int *) * numRows);
    *returnSize = numRows;
    // printf("returnSize = %d\n", *returnSize);
    *returnColumnSizes = malloc (sizeof (int) * numRows);
    for (int i = 1; i <= numRows; i++) {
        s = malloc(sizeof(int) * i);
        // printf("Current line:");
        for (int j = 0; j < i; j ++) {
            if (j == 0 || j == i-1) {
                s[j] = 1;
            } else {
                s[j] = res[i-2][j] + res[i-2][j-1];
            }
            // printf(" %d", s[j]);
        }
        res[i-1] = s;
        (*returnColumnSizes)[i-1] = i;
        // printf("| returnColumnSizes = %d\n", (*returnColumnSizes)[i-1]);
    }
    return res;
}

Last update : September 9, 2023
Created : August 16, 2023