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:

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

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

1 <= numRows <= 30

Although the algorithm is very simple, the iterative approach to constructing Pascal's triangle can be classified as dynamic programming because we construct each row based on the previous row.

First, we generate the overall triangle list, which will store each row as a sublist. Then, we check for the special case of 0, as we would otherwise return [1]. Since numRows is always greater than 0, we can initialize triangle with [1]

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> output = new ArrayList<>();
        output.add(new ArrayList<>());
        output.get(0).add(1);
        for(int i=1;i<numRows;i++){
            List<Integer> row = new ArrayList<>();
            List<Integer> prevRow = output.get(i-1);

            row.add(1);
            for(int j=1;j<i;j++){
                row.add(prevRow.get(j-1)+prevRow.get(j));
            }
            row.add(1);
            output.add(row);
        }
        return output;
    }
}

Time complexity: O(numRows 2 )

Although updating each value of triangle happens in constant time, it is performed O(numRows 2 ) times. To see why, consider how many overall loop iterations there are. The outer loop obviously runs numRows times, but for each iteration of the outer loop, the inner loop runs rowNum times. Therefore, the overall number of triangle updates that occur is 1+2+3+…+numRows, which, according to Gauss' formula, is

2 numRows(numRows+1) ​

​

= 2 numRows 2 +numRows ​

= 2 numRows 2

​ + 2 numRows ​

=O(numRows 2 ) ​

Space complexity: O(1)

While O(numRows 2 ) space is used to store the output, the input and output generally do not count towards the space complexity.