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
My Solution
We take care of the corner case, which is the first row with a 1. We then construct the Pascal’s Triangle up until the requested row index, but to save space, we don’t store the whole triangle. We only store the last row and keep replacing it as we add rows.
Time complexity would still be O(n²) because we iterate through n rows and each row has 1,2,3,…, up to n elements. Space complexity would only be O(n) however because we keep replacing the last row with the new row and only store one row at a time.
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> row = new ArrayList<>();
row.add(1);
for (int i = 1; i <= rowIndex; i++) {
List<Integer> next = new ArrayList<>();
next.add(1);
int n = row.size();
for (int j = 0; j < n-1; j++) {
next.add(row.get(j) + row.get(j+1));
}
next.add(1);
row = next;
}
return row;
}
}