Pascals Triangle

EasyArrays

Generate the first numRows rows of Pascal's triangle.

Constraints

1 <= numRows <= 30

Build row from the previous

Time O(numRows^2)Space O(numRows^2)

Each row starts and ends with 1. Every interior value at column c equals the sum of the two values above it in the previous row: prev[c-1] + prev[c]. Build the triangle row by row using the row just computed.

Key terms

Pascal's triangle:: A triangle of binomial coefficients where each entry sums the two above it.

vector<vector<int>> generate(int numRows) {
    vector<vector<int>> tri;
    for (int r = 0; r < numRows; r++) {
        vector<int> row(r + 1, 1);
        for (int c = 1; c < r; c++) row[c] = tri[r-1][c-1] + tri[r-1][c];
        tri.push_back(row);
    }
    return tri;
}

Step by step

For each row r (0-indexed), create a row of length r+1 filled with 1.
For interior columns c from 1 to r-1, set row[c] = prev[c-1] + prev[c].
Append the row to the triangle and use it as 'previous' for the next row.