Summary: In this programming example, we will learn three different ways to print pascal’s triangle in Java.

Method 1: Pascal’s Triangle using Combination

Each row in Pascal’s triangle is the coefficients of the binomial expansion i.e. (row-1)C(column-1)

pascal triangle in terms of binomial coefficients

We can easily calculate the value of (row-1)C(column-1) in Java and generate a pascal’s triangle.

All we need to do is to define a function which will return the value of (row-1)C(column-1) for the respective value of row and column.

Here is the implementation of the method in Java:

Output:

Java Pascal Triangle Program output

The time complexity of this method is O(n3) because, for each term inside 2 loops, we are calling a combination function which itself uses a for loop to calculate the value of nCr.

We can reduce the complexity of this program using a 2D array.

Method 2: Pascal’s Triangle using Array

If we notice the triangle carefully we observe that each entry in Pascal’s triangle is the sum of two values of the previous row.

Pascal Triangle Java
Source: Wikipedia

Hence we can use a 2D array to compute and store the value of each term from previously generated values and then output the array which will contain pascal’s triangle’s values.

Output:

Java Pascal Triangle Program output

The time and space complexity of this method is O(n2) and O(n) respectively.

The space complexity is because of the use of an extra array.

We can reduce the space complexity of this program by not using the array.

Method 3: Pascal Triangle without Array

The formula for each term of Pascal’s triangle except the first and last element of each row (which is always 1) is t=t*(i-j +1)/j

where ‘i’ represent the row, ‘j’ represent the column and ‘t’ represents the last term value.

All we need to do is to check the row and column index of each term inside the nested loop. If it is the first row or first column (i.e. if(j==0 || i==j)) we will simply output 1 otherwise we will output the value of t*(i-j +1)/j.

Here is the implementation of the method in Java:

Output:

Java Pascal Triangle Program output

The time and space complexity of the above program is O(n2) and O(1) respectively.

In this tutorial, we learned with examples the different ways to print the Pascal’s triangle using Java programming language.

Leave a Reply