Pascal's Triangle

Problem

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

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

Solution

In Place Row Solution: O(n^2) time and O(n) space

public class Solution {
    public List<List<Integer>> generate(int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> row = new ArrayList<>();
        while (n-- > 0) {
            row.add(0, 1);
            for (int i = 1; i < row.size() - 1; i++) { //we don't update until the third row
                row.set(i, row.get(i) + row.get(i + 1));
            }
            res.add(new ArrayList<>(row));
        }
        return res;
    }
}

Analysis

This is a problem about generating
We notice from the given example that each time row[i] = row[i] + row[i + 1]
Where i starts from 1 and ends at the second last index
We implement this by using loop: for(int i = 1; i < row.size() - 1; i++)
It's all about observation yo