# Pascal’s Triangle

In mathematics, Pascal’s triangle is a triangular array of the binomial coefficients. It can also be viewed as: each number in Pascal’s triangle is the sum of the two numbers directly above it as shown:

          1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1 

Problem

Given an integer n as input, print first n lines of the Pascal’s triangle.

###### Approach
Let's consider Pascal's triangle as a matrix pascal[i][j] in the following way:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1 

We could solve this problem using Dynamic Programming.

Optimal substructure

From the above matrix we could see that:

pascal[i][j] is the sum of previous element in the row i-1 and element just above the current element in the row i-1. Consider out of bound indices as 0
ie pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]

Code Implementation

//
//  main.cpp
//  Pascal Triangle
//
//  Created by Himanshu on 20/09/21.
//

#include <iostream>
using namespace std;

void printPascalTriangle (int n) {
int pascal[n+1][n+1];

//Base case
pascal = 1;

for (int i=0; i<=n; i++) {
for (int j=0; j<=n; j++) {
pascal[i][j] = 0;
}
}

for (int i=1; i<=n; i++) {
for (int j=1; j<=i; j++) {
// first and last binomial coefficients are
// always 1
if (i == 1 || j == i) {
pascal[i][j] = 1;
} else {
pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
}
}
}

for (int i=1; i<=n; i++) {
for (int j=1; j<=i; j++) {
cout<<pascal[i][j]<<" ";
}
cout<<endl;
}

}

int main() {
int n = 7;
printPascalTriangle (n);

return 0;
}



Output

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1 

Time Complexity: O(n2)
Auxiliary Space: O(n2)

Here’s a working example: Pascal’s Triangle

###### Approach with O(1) auxiliary space

By using the definition of binomial coefficient: we know that

C(n, i) = (n!)/((n-i)! * i!)
similarly,
C(n, i-1) = (n!)/((n-(i-1))! * (i-1)!)

Now, C(n, i) could also be written as (multiplying and dividing by (n-(i-1))):
((n!)*(n-(i-1)))/(n-(i-1))!*(i)*(i-1)!
which is nothing but
(n!)*(n-(i-1))/((n-(i-1))!*(i-1)!*(i)) ie,
C(n, i) =  C(n, i-1)*(n-(i-1))/(i)

Using the above equation, we just need the previous binomial coefficient C(n, i-1) to calculate C(n, i). Hence we need not save all the binomial coefficients to print current coefficient.

Code Implementation

//
//  main.cpp
//  Pascal Triangle 2
//
//  Created by Himanshu on 20/09/21.
//

#include <iostream>
using namespace std;

void printPascalTriangle (int n) {

//Base case
cout<<"1"<<endl;

for (int i=1; i<n; i++) {
int C = 1;
for (int j=0; j<=i; j++) {

cout<<C<<" ";
//We are using (i-j) instead of (i-(j-1)) because
//calculation is for next or (j+1)th element
C = C * (i-j)/(j+1);
}
cout<<endl;
}

}

int main() {
int n = 7;
printPascalTriangle (n);
return 0;
}


Output

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1 

Time Complexity: O(n2)
Auxiliary Space: O(1)

Here’s a working example: Pascal’s Triangle

Practice Problem
Pascal’s Triangle [LeetCode]