EPI(Elements of Programming Interviews) 6.24 - First n rows Pascal Triangle
Return the first n rows of Pascal's Triangle
Pascal's triangle is a triangular array of the binomial coefficients.
A simple construction of the triangle proceeds in the following manner. On row 0, write only the number 1. Then, to construct the elements of following rows, add the number above and to the left with the number above and to the right to find the new value. If either the number to the right or left is not present, substitute a zero in its place.
public static List<List<Integer>> generatePascalTriangle(int n) {
if (n <= 0) {
return Collections.emptyList();
}
List<Integer> prevRow = new ArrayList<>();
prevRow.add(1);
List<List<Integer>> result = new ArrayList<>();
result.add(prevRow);
for (int i = 1; i < n; ++i) {
List<Integer> currRow = new ArrayList<>();
currRow.add(1); // For the first element.
for (int j = 1; j < i; ++j) {
// Set this entry to the sum of the two above adjacent entries.
currRow.add(prevRow.get(j - 1) + prevRow.get(j));
}
currRow.add(1); // For the last element.
// Swaps the contents of prevRow and currRow.
List<Integer> temp = prevRow;
prevRow = currRow;
currRow = temp;
result.add(prevRow);
}
return result;
}
Return the first n rows of Pascal's Triangle
Pascal's triangle is a triangular array of the binomial coefficients.
A simple construction of the triangle proceeds in the following manner. On row 0, write only the number 1. Then, to construct the elements of following rows, add the number above and to the left with the number above and to the right to find the new value. If either the number to the right or left is not present, substitute a zero in its place.
This construction is related to the binomial coefficients by Pascal's rule:
public static List<List<Integer>> generatePascalTriangle(int n) {
if (n <= 0) {
return Collections.emptyList();
}
List<Integer> prevRow = new ArrayList<>();
prevRow.add(1);
List<List<Integer>> result = new ArrayList<>();
result.add(prevRow);
for (int i = 1; i < n; ++i) {
List<Integer> currRow = new ArrayList<>();
currRow.add(1); // For the first element.
for (int j = 1; j < i; ++j) {
// Set this entry to the sum of the two above adjacent entries.
currRow.add(prevRow.get(j - 1) + prevRow.get(j));
}
currRow.add(1); // For the last element.
// Swaps the contents of prevRow and currRow.
List<Integer> temp = prevRow;
prevRow = currRow;
currRow = temp;
result.add(prevRow);
}
return result;
}