# 118. Pascal's Triangle (Easy)

https://leetcode.com/problems/pascals-triangle/

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

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

Example:

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

## Solutions

### 2.

``````class Solution {

public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ans = new ArrayList<>();

Map<String, Integer> track = new HashMap<>();

for (int i = 1; i <= numRows; i++) {
List<Integer> levelI = new ArrayList<>();

for (int j = 1; j <= i; j++) {
int val = pascal(i, j, track);

}

}

return ans;
}

private int pascal(int i, int j, Map<String, Integer> track) {
String key = i + "#" + j;

if (j == 1 || j == i) {
track.put(key, 1);
return 1;
}

if (track.containsKey(key)) {
return track.get(key);
}

int left = track.get((i - 1) + "#" + (j - 1));
int right = track.get((i - 1) + "#" + (j));

int val = left + right;

track.put(key, val);

return val;
}
}
``````

### 2.

``````class Solution {

// BigInteger is not efficient. It's the last choice you can pick.

public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ans = new ArrayList<>();

for (int i = 1; i <= numRows; i++) {
List<Integer> levelI = new ArrayList<>();

for (int j = 1; j <= i; j++) {
int val = (int)(pascal(i, j));

}

}

return ans;
}

private long pascal(long i, long j) {
if (j == 1 || j == i) {
return 1;
}

i--;
j--;

BigInteger x1 = rank(i, j);
BigInteger x2 = rank(i - j, 1);

return x1.divide(x2).intValue();
}

// Be careful with overflow issue of rank computation
private BigInteger rank(long r, long j) {
BigInteger ans = BigInteger.valueOf(1);

while (r > j) {
ans = ans.multiply(BigInteger.valueOf(r));
r--;
}

return ans;
}
}
``````