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);

                    levelI.add(val);
               }

               ans.add(levelI);
          }

          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));

                    levelI.add(val);
               }

               ans.add(levelI);
          }

          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;
     }
}

Incorrect Solutions

References