Pascal's Triangle

easy array dp

Problem

Return the first numRows of Pascal's triangle. Row 0 is [1]; each subsequent row[k] = prev[k-1] + prev[k] with prev[−1] = prev[len] = 0.

InputnumRows = 5

Output[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Each interior entry is the sum of the two values directly above it.

numRows

def generate(numRows):
    rows = []
    for i in range(numRows):
        row = [1] * (i + 1)
        for j in range(1, i):
            row[j] = rows[i - 1][j - 1] + rows[i - 1][j]
        rows.append(row)
    return rows

function generate(numRows) {
  const rows = [];
  for (let i = 0; i < numRows; i++) {
    const row = new Array(i + 1).fill(1);
    for (let j = 1; j < i; j++) {
      row[j] = rows[i - 1][j - 1] + rows[i - 1][j];
    }
    rows.push(row);
  }
  return rows;
}

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> rows = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) row.add(1);
            for (int j = 1; j < i; j++) row.set(j, rows.get(i - 1).get(j - 1) + rows.get(i - 1).get(j));
            rows.add(row);
        }
        return rows;
    }
}

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> rows;
        for (int i = 0; i < numRows; i++) {
            vector<int> row(i + 1, 1);
            for (int j = 1; j < i; j++) row[j] = rows[i - 1][j - 1] + rows[i - 1][j];
            rows.push_back(row);
        }
        return rows;
    }
};

Explanation

Pascal's triangle has a simple building rule: every interior number is the sum of the two numbers directly above it, and the edges are always 1. We just generate each row in turn and collect them.

For row i we create a list of i + 1 ones. The first and last stay 1 automatically; only the inner positions need real work.

For each inner index j (from 1 up to i-1) we set row[j] = rows[i-1][j-1] + rows[i-1][j] — the two values sitting above it in the previous row. Once the row is filled, we push it into rows.

Example with numRows = 5: row 0 is [1], row 1 is [1, 1], and row 2's middle is 1 + 1 = 2 giving [1, 2, 1]. Continuing gives [1, 3, 3, 1] and [1, 4, 6, 4, 1].

Because each new row only looks at the row just above it, we build the whole triangle from the top down in one straightforward sweep.

Time: O(numRows²) Space: O(numRows²) for the output