Dare2Solve
Given an integer rowIndex
, return the rowIndex
-th (0-indexed) row of Pascal's Triangle.
In Pascal's Triangle, each number is the sum of the two numbers directly above it.
Pascal's Triangle is a well-known mathematical construct where each row represents the coefficients of the binomial expansion. The rowIndex
-th row can be generated iteratively by leveraging the relationship between the elements of consecutive rows.
Initialization:
result
of size rowIndex + 1
, initialized with zeros. Set the first element to 1
because the first element of each row in Pascal's Triangle is always 1
.Iterative Construction:
1
to rowIndex
, update the result
array in reverse order to avoid overwriting values that are yet to be used.i
in the row, update result[i]
as result[i] + result[i-1]
.Final Output:
result
array contains the values of the rowIndex
-th row of Pascal's Triangle.(O(n^2)), where n
is the rowIndex
. This is due to the nested loop where each element in a row is computed based on the previous row.
(O(n)), where n
is the rowIndex
. Only a single array of size rowIndex + 1
is used to store the row values.
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> result(rowIndex + 1, 0);
result[0] = 1;
for (int row = 1; row <= rowIndex; ++row) {
result[row] = 1;
for (int index = row - 1; index > 0; --index) {
result[index] += result[index - 1];
}
}
return result;
}
};
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
result = [0] * (rowIndex + 1)
result[0] = 1
for row in range(1, rowIndex + 1):
result[row] = 1
for index in range(row - 1, 0, -1):
result[index] += result[index - 1]
return result
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> result = new ArrayList<>(Collections.nCopies(rowIndex + 1, 0));
result.set(0, 1);
for (int row = 1; row <= rowIndex; ++row) {
result.set(row, 1);
for (int index = row - 1; index > 0; --index) {
result.set(index, result.get(index) + result.get(index - 1));
}
}
return result;
}
}
function getRow(rowIndex) {
const result = new Int32Array(rowIndex + 1);
result[0] = 1;
for (let row = 1; row <= rowIndex; ++row) {
result[row] = 1;
for (let index = row - 1; index > 0; --index) {
result[index] += result[index - 1];
}
}
return result;
}