118. Pascal's Triangle

Problem Link

Description

---

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

 

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

 

Constraints:

• 1 <= numRows <= 30

Solution

---

Python3

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        A = [[1] * (i + 1) for i in range(numRows)]
        
        for row in range(2, numRows):
            for j in range(1, len(A[row]) - 1):
                A[row][j] = A[row - 1][j - 1] + A[row - 1][j]
        
        return A

Java

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        ArrayList<Integer> pre = null;
        for (int i = 1; i <= numRows; i++) {
            ArrayList<Integer> save = new ArrayList<>();
            for (int j = 1; j <= i; j++)
                if (j == 1 || j == i) save.add(1);
                else save.add(pre.get(j-1) + pre.get(j-2));
            result.add(save);
            pre = save;
        }
        return result;
    }
}