Interview 150
Pascal's Triangle
- Problem
- LC 118
- File
- interview150_LC118PascalsTriangle.java
- Path
- pkg5leetcode/interview150/interview150_LC118PascalsTriangle.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC118PascalsTriangle.java
- Approach
- Each row built from previous row sums of adjacent pairs.
- Complexity
- Time O(n^2), Space O(n^2)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Pascal's Triangle | LC 1185 * APPROACH: Each row built from previous row sums of adjacent pairs.6 * COMPLEXITY: Time O(n^2), Space O(n^2)7 */8import java.util.*;9 10public class interview150_LC118PascalsTriangle {11 static List<List<Integer>> generate(int numRows) {12 List<List<Integer>> res = new ArrayList<>();13 for (int i = 0; i < numRows; i++) {14 List<Integer> row = new ArrayList<>();15 for (int j = 0; j <= i; j++) {16 if (j == 0 || j == i) row.add(1);17 else row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));18 }19 res.add(row);20 }21 return res;22 }23 24 public static void main(String[] args) {25 List<List<Integer>> g = generate(3);26 check(g.size() == 3 && g.get(2).equals(Arrays.asList(1, 2, 1)), "case1");27 check(generate(1).get(0).equals(Arrays.asList(1)), "case2");28 System.out.println("all tests passed");29 }30 31 static void check(boolean cond, String name) {32 if (!cond) throw new AssertionError("FAILED: " + name);33 System.out.println(" PASS " + name);34 }35}