[LeetCode] 118. Pascals Triangle

Posted on | In

Problem

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

118. Pascal's Triangle

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

1
2
3
4
5
6
7
8
9
Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Explanation

  1. After observing the triangle. We find out that each row, the first column value and the last column value is always 1, and the number of column is equal to the number of row.

  2. In each row, we have the formula to calculate the current number’s value: $currVal = prevVal * (currRow - prevCol) / prevCol$ (Row index and column index start from 1).

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();

        for (int row = 1; row <= numRows; row++) {
            List<Integer> rowLst = new ArrayList<>();
            rowLst.add(1);
            for (int preCol = 1; preCol < row; preCol++) {
                int preNum = rowLst.get(rowLst.size()-1);
                int curNum = preNum * (row - preCol) / preCol;
                rowLst.add(curNum);
            }
            res.add(rowLst);
        }

        return res;
    }
}