107. Pascal's Triangle II

Row r of Pascal's triangle is built from row r-1: each interior entry is the sum of the two entries above it. Update a single array in place from right to left so each addition uses the still-un-overwritten previous-row values.

Build row by row

Every row starts and ends with 1, and each interior value is the sum of the two values above it in the previous row. Keep just one array row and rebuild it rowIndex times.

Update from the right to reuse in place

If you update right to left, row[j] += row[j-1] still sees the old (previous-row) row[j-1], so you never need a second array:

row = [1]
for _ in range(rowIndex):
    row.append(1)                      # extend with the trailing 1
    for j in range(len(row)-2, 0, -1):
        row[j] += row[j-1]
return row

Worked example

rowIndex = 4.

• start [1]
• [1,1]
• [1,2,1]
• [1,3,3,1]
• [1,4,6,4,1]

Return [1, 4, 6, 4, 1].

Complexity

• Time: O(rowIndex^2).
• Space: O(rowIndex) — a single row array (the output).

class Solution {
    public int[] getRow(int rowIndex) {
        int[] row = new int[rowIndex + 1];
        row[0] = 1;
        for (int r = 1; r <= rowIndex; r++) {
            for (int j = r; j > 0; j--) {
                row[j] += row[j - 1];
            }
        }
        return row;
    }
}