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][1] = 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(n²)
Auxiliary Space: O(n²)

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(n²)
Auxiliary Space: O(1)

Here’s a working example: Pascal’s Triangle

Practice Problem
Pascal’s Triangle [LeetCode]