# Pascal's Triangle (118)

**Example:**

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

**Approach:** 

Pascal's triangle is essentially the embodiment of dynamic programming as we can construct each row based on the value of the previous one.

* We first generate an overall Triangle list which stores all the sublist rows.
* We add \[1] in the triangle as it's first row and proceed to make the calculations for the subsequent rows.
* We''ll have an Outer loop: `(# of rows of triangle)` as well as an Inner loop: `(Taking care of row calculations).`
* As we're dealing with the rows in the Inner loop, *(Barring element 1 and element n - 1)* each element of a present row is equal to the sum of the `above element + above element + 1.`

```java
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> allRows = new ArrayList<>();
        List<Integer> row = new ArrayList<>();
        
        for(int i = 0; i < numRows; i++){
            row.add(0, 1);
            for(int j = 1; j < row.size() - 1; j++){
                row.set(j, row.get(j) + row.get(j + 1));
            }
            allRows.add(new ArrayList<Integer>(row));
        }
        return allRows;
    }
}
```

**`Amortized Complexity: O(N2) time`**

&#x20;*\*\*Since Java's ArrayList allocates the required memory in chunks (typically by doubling the size when it hits the limit), we can say that ArrayList.add() has O(1) "amortized" time complexity.*