119. Pascal’s Triangle II
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: rowIndex = 3
Output: [1,3,3,1]
Example 2:
Input: rowIndex = 0
Output: [1]
Example 3:
Input: rowIndex = 1
Output: [1,1]
Constraints:
- 0 <= rowIndex <= 33
From: LeetCode
Link: 119. Pascal’s Triangle II
Solution:
Ideas:
1. Memory Allocation: The function uses malloc to allocate memory for the array that will store the rowIndex-th row. The size of the array is rowIndex + 1.
2. Initialization: The first element of each row is always 1, so row[0] = 1.
3. Calculating Row Elements:
- The outer loop runs from 1 to rowIndex to construct each row up to the desired rowIndex.
- Inside the outer loop, the last element of each row is set to 1.
- The inner loop updates the elements of the row in reverse order (from right to left) to avoid overwriting the values needed for the calculations. Each element row[j] is updated as the sum of row[j] and row[j-1].
4. Returning the Result: The function returns the pointer to the array containing the desired row.
Code:
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* getRow(int rowIndex, int* returnSize) {
*returnSize = rowIndex + 1;
int* row = (int*)malloc((*returnSize) * sizeof(int));
row[0] = 1; // The first element is always 1
for (int i = 1; i <= rowIndex; i++) {
row[i] = 1; // The last element in each row is always 1
for (int j = i - 1; j > 0; j--) {
row[j] = row[j] + row[j - 1];
}
}
return row;
}