Pascal's Triangle II
Problem
Return row rowIndex (0-indexed) of Pascal's triangle using O(rowIndex) extra space.
rowIndex = 3[1, 3, 3, 1]def getRow(rowIndex):
row = [1] * (rowIndex + 1)
for i in range(1, rowIndex + 1):
for j in range(i - 1, 0, -1):
row[j] = row[j] + row[j - 1]
return rowfunction getRow(rowIndex) {
const row = new Array(rowIndex + 1).fill(1);
for (let i = 1; i <= rowIndex; i++) {
for (let j = i - 1; j > 0; j--) {
row[j] = row[j] + row[j - 1];
}
}
return row;
}class Solution {
public List<Integer> getRow(int rowIndex) {
Integer[] row = new Integer[rowIndex + 1];
Arrays.fill(row, 1);
for (int i = 1; i <= rowIndex; i++) {
for (int j = i - 1; j > 0; j--) {
row[j] = row[j] + row[j - 1];
}
}
return Arrays.asList(row);
}
}class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + 1, 1);
for (int i = 1; i <= rowIndex; i++) {
for (int j = i - 1; j > 0; j--) {
row[j] = row[j] + row[j - 1];
}
}
return row;
}
};Explanation
We only need one specific row of Pascal's triangle, and we want to do it using just a single array instead of building the whole triangle. The trick is to keep folding the same row in place.
We start with a row of all ones, [1, 1, ..., 1] of length rowIndex + 1. Then for each level i from 1 up to rowIndex, we update the row so it becomes the next level down.
The crucial detail is iterating right to left with row[j] = row[j] + row[j-1]. Going right to left means that when we update row[j], the value row[j-1] still holds the previous level's number (we have not overwritten it yet). The two ends always stay 1.
Example: for rowIndex = 3 we start at [1, 1, 1, 1]. Folding gives [1, 2, 1, 1], then [1, 3, 3, 1] — which is the answer.
Each entry equals the sum of the two numbers above it, exactly matching Pascal's rule, but we reuse one array so the extra space stays small.