118. Pascal's Triangle

Description

Generate the first numRows of Pascal's triangle. Each row in Pascal's triangle is created by summing adjacent elements of the previous row, starting with the first row as [1].

Intuition

Pascal's triangle is constructed using a simple rule: each element is the sum of the two elements directly above it in the previous row. The first and last elements of each row are always 1.

Approach

1. Initialize the result list with the first row [1].
2. Iterate from 0 to numRows - 1 to construct each row.
3. For each row, create a dummyRow by padding the previous row with zeros at both ends.
4. Sum adjacent elements in dummyRow to generate the new row.
5. Append the new row to the result list.
6. Continue this process until all rows are generated.

Complexity

Time complexity:

O(numRows^2), because generating each row involves iterating through the elements of the previous row.

Space complexity:

O(numRows^2), because we store all rows of the triangle in the result list.

Code

C++

class Solution {
public:
    vector> generate(int numRows) {
        vector> res = {{1}};
        for (int i = 0; i < numRows - 1; ++i) {
            vector dummyRow = {0};
            dummyRow.insert(dummyRow.end(), res.back().begin(), res.back().end());
            dummyRow.push_back(0);
            
            vector row;
            for (int j = 0; j < dummyRow.size() - 1; ++j) {
                row.push_back(dummyRow[j] + dummyRow[j + 1]);
            }
            res.push_back(row);
        }
        return res;
    }
};

Python

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = [[1]]
        
        for i in range(numRows - 1):
            prev_row = res[-1]
            dummy_row = [0] + prev_row + [0]
            row = []
            for j in range(len(dummy_row) - 1):
                row.append(dummy_row[j] + dummy_row[j + 1])
            res.append(row)
        
        return res

Java

class Solution {
    public List> generate(int numRows) {
        List> res = new ArrayList<>();
        res.add(new ArrayList<>(Arrays.asList(1)));
        
        for (int i = 0; i < numRows - 1; i++) {
            List prevRow = res.get(res.size() - 1);
            List dummyRow = new ArrayList<>();
            dummyRow.add(0);
            dummyRow.addAll(prevRow);
            dummyRow.add(0);
            
            List row = new ArrayList<>();
            for (int j = 0; j < dummyRow.size() - 1; j++) {
                row.add(dummyRow.get(j) + dummyRow.get(j + 1));
            }
            res.add(row);
        }
        
        return res;
    }
}

JavaScript

var generate = function (numRows) {
    const res = [[1]];
    for (let i = 0; i < numRows - 1; i++) {

        const dummyRow = [0, ...res[res.length - 1], 0];
        const row = [];
        for (let j = 0; j < dummyRow.length - 1; j++) {
            
            row.push(dummyRow[j] + dummyRow[j + 1]);
        }
        res.push(row);
    }
    return res;
};