SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

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<vector<int>> generate(int numRows) {
        vector<vector<int>> res = {{1}};
        for (int i = 0; i < numRows - 1; ++i) {
            vector<int> dummyRow = {0};
            dummyRow.insert(dummyRow.end(), res.back().begin(), res.back().end());
            dummyRow.push_back(0);
            
            vector<int> 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<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>(Arrays.asList(1)));
        
        for (int i = 0; i < numRows - 1; i++) {
            List<Integer> prevRow = res.get(res.size() - 1);
            List<Integer> dummyRow = new ArrayList<>();
            dummyRow.add(0);
            dummyRow.addAll(prevRow);
            dummyRow.add(0);
            
            List<Integer> 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;
};