[LeetCode] Problem 118 - Pascal's Triangle

Posted on | In ,

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

EpVNMq.gif

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

Example

Input: 5

Output:

1
2
3
4
5
6
7
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> triangle = new ArrayList<>();
    
    if (numRows == 0)
        return triangle;
    
    triangle.add(new ArrayList<>());
    triangle.get(0).add(1);

    for (int num = 1; num < numRows; num++) {
        List<Integer> row = new ArrayList<>();
        List<Integer> prev = triangle.get(num - 1);
        row.add(1);

        for (int i = 1; i < num; i++)
            row.add(prev.get(i - 1) + prev.get(i));

        row.add(1);
        triangle.add(row);
    }

    return triangle;
}