Given an integer n, return the first n rows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it, as shown in the figure below:
Input: n=5
Output:
1 1,1 1,2,1 1,3,3,1 1,4,6,4,1
Input: n=3
Output:
1 1,1 1,2,1
Solutions
Method 1: In O(n^2) time and O(n^2) space
We can see that each ith row requires i columns, and the first and last elements in each row have 1 as an element.
We can also see that the 2nd to n-2nd elements are simply the sum of the ith and i-1 nt elements from the previous row.
Now to print Pascal's Triangle of n rows, we need to follow the below steps:
1) Begin a loop that goes from 0 to n-1 (number of rows).
2) For each iteration, create an array of length n.
3) Set the 0th and n-1st elements to 1.
4) For the remaining elements, from the first to the n-2nd, enter the value arr [i] = prev [i] + prev [i-1].
5) Print current array arr[].
6) Assign current array arr[] to previous array prev[] for use in the next iteration.
Complexity
The time complexity of this solution is O(n^2) and space complexity is O(n^2).