Generate pascal triangle of the given size
Given a non-negative integer n, print the first n rows of Pascal’s triangle.
Each number in Pascal’s triangle is constructed by adding the two numbers diagonally above, where blank entries being interpreted as 0. For instance, the first eight rows of Pascal’s triangle are depicted in the diagram below.
For example,
Output: [[1], [1, 1], [1, 2, 1]]
Input: n = 5
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
We can easily solve this problem using dynamic programming. The idea is to calculate the subsequent row of Pascal’s triangle using the values of its previous row. With the exception of the first and last, each member of the row can be calculated by adding the element directly above it and the preceding element before the top element. The first and last elements of each row are always ones, and the first row only has one element, which is also one.
Following is the C++, Java, and Python implementation based on the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <iostream> #include <vector> using namespace std; vector<vector<int>> getPascalTriangleElements(int n) { // create vector of vectors to store result vector<vector<int>> rows(n); // base case if (n <= 0) { return rows; } // do for each row for (int i = 0; i < n; i++) { // resize the current row, and initialize all its elements by 1 rows[i].resize(i + 1, 1); // do for all elements except the first and the last for (int j = 1; j < i; j++) { // sum adjacent elements in the preceding row rows[i][j] = rows[i - 1][j - 1] + rows[i - 1][j]; } } // return the result return rows; } int main() { int n = 5; vector<vector<int>> rows = getPascalTriangleElements(n); // print vector for (auto const &row: rows) { for (auto const &i: row) { cout << i << " "; } cout << endl; } return 0; } |
Output:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import java.util.ArrayList; import java.util.List; class Main { public static List<List<Integer>> getPascalTriangleElements(int n) { List<List<Integer>> rows = new ArrayList<>(); // base case if (n <= 0) { return rows; } // base case: first row contains only a single element 1 rows.add(List.of(1)); // do for each row starting the second row for (int i = 1; i < n; i++) { List<Integer> row = new ArrayList<>(); for (int j = 0; j <= i; j++) { // first and last element of any row will be always 1 if (j == 0 || j == i) { row.add(1); } else { // for all other elements, sum adjacent elements in the preceding row List<Integer> prev = rows.get(i - 1); row.add(prev.get(j - 1) + prev.get(j)); } } // add current row to the result rows.add(row); } return rows; } public static void main(String[] args) { int n = 5; List<List<Integer>> result = getPascalTriangleElements(n); System.out.println(result); } } |
Output:
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
def getPascalTriangleElements(n): rows = [] # base case if n <= 0: return rows # base case: first row contains only a single element 1 rows.append([1]) # do for each row starting the second row for i in range(1, n): row = [] for j in range(0, i + 1): # first and last element of any row will be always 1 if j == 0 or j == i: row.append(1) else: # for all other elements, sum adjacent elements in the preceding row prev = rows[i - 1] row.append(prev[j - 1] + prev[j]) # add current row to the result rows.append(row) return rows if __name__ == '__main__': n = 5 result = getPascalTriangleElements(n) print(result) |
Output:
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
The time complexity of the above solution is O(n) and requires O(n) extra space.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)