Pascal's Triangle (118)

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

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.

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

**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.