# Pascal’s Triangle

Pascal’s triangle is a triangular array of the binomial coefficients. Write a function that takes an integer value n as input and prints first n lines of the Pascal’s triangle. Following are the first 6 rows of Pascal’s Triangle.

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

## We strongly recommend that you click here and practice it, before moving on to the solution.

Method 1 ( O(n^3) time complexity )
Number of entries in every line is equal to line number. For example, the first line has “1”, the second line has “1 1”, the third line has “1 2 1”,.. and so on. Every entry in a line is value of a Binomial Coefficient. The value of ith entry in line number line is C(line, i). The value can be calculated using following formula.

C(line, i)   = line! / ( (line-i)! * i! )

A simple method is to run two loops and calculate the value of Binomial Coefficient in inner loop.

## C++

 //  C++ code for Pascal's Triangle #include    // See https://tutorialspoint.dev/slugresolver/space-and-time-efficient-binomial-coefficient/  // for details of this function int binomialCoeff(int n, int k);    // Function to print first // n lines of Pascal's  // Triangle void printPascal(int n) {     // Iterate through every line and     // print entries in it     for (int line = 0; line < n; line++)     {         // Every line has number of          // integers equal to line          // number         for (int i = 0; i <= line; i++)             printf("%d ",                     binomialCoeff(line, i));         printf(" ");     } }    // See https://tutorialspoint.dev/slugresolver/space-and-time-efficient-binomial-coefficient/ // for details of this function int binomialCoeff(int n, int k) {     int res = 1;     if (k > n - k)     k = n - k;     for (int i = 0; i < k; ++i)     {         res *= (n - i);         res /= (i + 1);     }            return res; }    // Driver program  int main() {     int n = 7;     printPascal(n);     return 0; }

## Java

 // Java code for Pascal's Triangle import java.io.*;    class GFG {            // Function to print first     // n lines of Pascal's Triangle     static void printPascal(int n)     {                // Iterate through every line     // and print entries in it     for (int line = 0; line < n; line++)     {         // Every line has number of          // integers equal to line number         for (int i = 0; i <= line; i++)         System.out.print(binomialCoeff                         (line, i)+" ");                                    System.out.println();     }     }            // Link for details of this function     static int binomialCoeff(int n, int k)     {         int res = 1;                    if (k > n - k)         k = n - k;                        for (int i = 0; i < k; ++i)         {             res *= (n - i);             res /= (i + 1);         }         return res;     }            // Driver code     public static void main(String args[])     {     int n = 7;     printPascal(n);     } }    /*This code is contributed by Nikita Tiwari.*/

/div>

## Python3

 # Python 3 code for Pascal's Triangle # A simple O(n^3)  # program for  # Pascal's Triangle    # Function to print  # first n lines of # Pascal's Triangle def printPascal(n) :            # Iterate through every line      # and print entries in it     for line in range(0, n) :                    # Every line has number of          # integers equal to line         # number         for i in range(0, line + 1) :             print(binomialCoeff(line, i),                 " ", end = "")         print()           # See https://tutorialspoint.dev/slugresolver/space-and-time-efficient-binomial-coefficient/ # for details of this function def binomialCoeff(n, k) :     res = 1     if (k > n - k) :         k = n - k     for i in range(0 , k) :         res = res * (n - i)         res = res // (i + 1)            return res    # Driver program n = 7 printPascal(n)       # This code is contributed by Nikita Tiwari.

## C#

 // C# code for Pascal's Triangle using System;    class GFG {            // Function to print first     // n lines of Pascal's Triangle     static void printPascal(int n)     {                // Iterate through every line     // and print entries in it     for (int line = 0; line < n; line++)     {         // Every line has number of          // integers equal to line number         for (int i = 0; i <= line; i++)         Console.Write(binomialCoeff                         (line, i)+" ");                                    Console.WriteLine();     }     }            // Link for details of this function     static int binomialCoeff(int n, int k)     {         int res = 1;                    if (k > n - k)         k = n - k;                        for (int i = 0; i < k; ++i)         {             res *= (n - i);             res /= (i + 1);         }         return res;     }            // Driver code     public static void Main()     {     int n = 7;     printPascal(n);     } }    /*This code is contributed by vt_m.*/

## PHP

 \$n - \$k)     \$k = \$n - \$k;     for (\$i = 0; \$i < \$k; ++\$i)     {         \$res *= (\$n - \$i);         \$res /= (\$i + 1);     } return \$res; }    // Function to print first // n lines of Pascal's  // Triangle function printPascal(\$n) {     // Iterate through every line and     // print entries in it     for (\$line = 0; \$line < \$n; \$line++)     {         // Every line has number of          // integers equal to line          // number         for (\$i = 0; \$i <= \$line; \$i++)                 echo "".binomialCoeff(\$line, \$i)." ";                            echo " ";     } }    // Driver Code \$n=7; printPascal(\$n);    // This code is contributed by Mithun Kumar ?>

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 of this method is O(n^3). Following are optimized methods.

Method 2( O(n^2) time and O(n^2) extra space )
If we take a closer at the triangle, we observe that every entry is sum of the two values above it. So we can create a 2D array that stores previously generated values. To generate a value in a line, we can use the previously stored values from array.

## C++

 // C++ program for Pascal’s Triangle // A O(n^2) time and O(n^2) extra space  // method for Pascal's Triangle #include using namespace std;    void printPascal(int n) {            // An auxiliary array to store      // generated pscal triangle values     int arr[n][n];         // Iterate through every line and      // print integer(s) in it     for (int line = 0; line < n; line++)     {         // Every line has number of integers          // equal to line number         for (int i = 0; i <= line; i++)         {         // First and last values in every row are 1         if (line == i || i == 0)             arr[line][i] = 1;         // Other values are sum of values just          // above and left of above         else             arr[line][i] = arr[line - 1][i - 1] +                              arr[line - 1][i];         cout << arr[line][i] << " ";         }         cout << " ";     } }    // Driver code int main() {     int n = 5;     printPascal(n);     return 0; }    // This code is Contributed by Code_Mech.

## C

 // C program for Pascal’s Triangle // A O(n^2) time and O(n^2) extra space  // method for Pascal's Triangle void printPascal(int n) { // An auxiliary array to store  // generated pscal triangle values int arr[n][n];     // Iterate through every line and print integer(s) in it for (int line = 0; line < n; line++) {     // Every line has number of integers      // equal to line number     for (int i = 0; i <= line; i++)     {     // First and last values in every row are 1     if (line == i || i == 0)         arr[line][i] = 1;     // Other values are sum of values just      // above and left of above     else          arr[line][i] = arr[line-1][i-1] + arr[line-1][i];     printf("%d ", arr[line][i]);     }     printf(" "); } } // Driver code int main() { int n = 5;     printPascal(n);     return 0; }

## Java

 // java program for Pascal's Triangle // A O(n^2) time and O(n^2) extra  // space method for Pascal's Triangle import java.io.*;    class GFG {     public static void main (String[] args) {         int n = 5;         printPascal(n);     }    public static void printPascal(int n) { // An auxiliary array to store generated pascal triangle values int[][] arr = new int[n][n];     // Iterate through every line and print integer(s) in it for (int line = 0; line < n; line++) {     // Every line has number of integers equal to line number     for (int i = 0; i <= line; i++)     {     // First and last values in every row are 1     if (line == i || i == 0)         arr[line][i] = 1;     else // Other values are sum of values just above and left of above         arr[line][i] = arr[line-1][i-1] + arr[line-1][i];     System.out.print(arr[line][i]);     }     System.out.println(""); } } }

## C#

 // C# program for Pascal's Triangle // A O(n^2) time and O(n^2) extra  // space method for Pascal's Triangle using System;    class GFG  { public static void printPascal(int n) {        // An auxiliary array to store  // generated pascal triangle values int[,] arr = new int[n, n];     // Iterate through every line // and print integer(s) in it for (int line = 0; line < n; line++) {     // Every line has number of      // integers equal to line number     for (int i = 0; i <= line; i++)     {                // First and last values      // in every row are 1     if (line == i || i == 0)         arr[line, i] = 1;     else // Other values are sum of values          // just above and left of above         arr[line, i] = arr[line - 1, i - 1] +                         arr[line - 1, i];     Console.Write(arr[line, i]);     } Console.WriteLine(""); } }    // Driver Code public static void Main ()  {     int n = 5;     printPascal(n); } }    // This code is contributed  // by Akanksha Rai(Abby_akku)

## PHP



Output:

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

This method can be optimized to use O(n) extra space as we need values only from previous row. So we can create an auxiliary array of size n and overwrite values. Following is another method uses only O(1) extra space.

Method 3 ( O(n^2) time and O(1) extra space )
This method is based on method 1. We know that ith entry in a line number line is Binomial Coefficient C(line, i) and all lines start with value 1. The idea is to calculate C(line, i) using C(line, i-1). It can be calculated in O(1) time using the following.

C(line, i)   = line! / ( (line-i)! * i! )
C(line, i-1) = line! / ( (line - i + 1)! * (i-1)! )
We can derive following expression from above two expressions.
C(line, i) = C(line, i-1) * (line - i + 1) / i

So C(line, i) can be calculated from C(line, i-1) in O(1) time

## C++

 // C++ program for Pascal’s Triangle // A O(n^2) time and O(1) extra space  // function for Pascal's Triangle #include    using namespace std; void printPascal(int n) {        for (int line = 1; line <= n; line++) {     int C = 1; // used to represent C(line, i)     for (int i = 1; i <= line; i++)      {                    // The first value in a line is always 1         cout<< C<<" ";          C = C * (line - i) / i;      }     cout<<" "; } }    // Driver code int main() {     int n = 5;     printPascal(n);     return 0; }    // This code is contributed by Code_Mech

## C

 // C program for Pascal’s Triangle // A O(n^2) time and O(1) extra space  // function for Pascal's Triangle void printPascal(int n) { for (int line = 1; line <= n; line++) {     int C = 1; // used to represent C(line, i)     for (int i = 1; i <= line; i++)      {     printf("%d ", C); // The first value in a line is always 1     C = C * (line - i) / i;      }     printf(" "); } } // Driver code int main() { int n = 5;     printPascal(n);     return 0; }

## Java

 // Java program for Pascal's Triangle // A O(n^2) time and O(1) extra  // space method for Pascal's Triangle import java.io.*; class GFG {    //Pascal function  public static void printPascal(int n) {     for(int line = 1; line <= n; line++)     {                int C=1;// used to represent C(line, i)     for(int i = 1; i <= line; i++)     {          // The first value in a line is always 1         System.out.print(C+" ");         C = C * (line - i) / i;      }     System.out.println();     } }    //Diver code public static void main (String[] args) {     int n = 5;     printPascal(n); }  } // This code is contributed  // by Archit Puri

## Python3

# Python3 program for Pascal’s Triangle
# A O(n^2) time and O(1) extra
# space method for Pascal’s Triangle

# Pascal function
def printPascal(n):

for line in range(1, n + 1):
C = 1; # used to represent C(line, i)
for i in range(1, line + 1):

# The first value in a
# line is always 1
print(C, end = ” “);
C = int(C * (line – i) / i);
print(“”);

# Driver code
n = 5;
printPascal(n);

# This code is contributed by mits

## C#

 // C# program for Pascal's Triangle  // A O(n^2) time and O(1) extra  // space method for Pascal's Triangle  using System; class GFG  {     // Pascal function  public static void printPascal(int n)  {      for(int line = 1;              line <= n; line++)      {                 int C = 1;// used to represent C(line, i)      for(int i = 1; i <= line; i++)      {          // The first value in a         // line is always 1          Console.Write(C + " ");          C = C * (line - i) / i;      }      Console.Write(" ") ;     }  }     // Driver code  public static void Main () {      int n = 5;      printPascal(n);  }  }     // This code is contributed // by ChitraNayal

## PHP



Output:

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

So method 3 is the best method among all, but it may cause integer overflow for large values of n as it multiplies two integers to obtain values.