Write a Java program to print the Pascal triangle pattern.

Pascal Triangle using Combination in Java

Each row in Pascal’s triangle is basically the binomial coefficients of the binomial expansion.

pascal triangle

So to do this we will define a function that will return the value of nCr for the respective value of n and r.

Recommended: How to find the combination (nCr) in Java?

Output

Java Pascal Triangle Program output

The time complexity of the above method is O(n^3) because, for each term (inside 2 loops), we are calling combination function which itself uses for loop to calculate and return the value of nCr.

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

Pascal Triangle using Array in Java

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 will output the array.

Output

Java Pascal Triangle Program output

The time complexity of the above program is O(n^2) but it requires extra space of O(n^1).

We can reduce the space complexity of the program by not using the array. Let’s see how to do it.

Pascal Triangle without Array in Java

The formula for each term of pascal 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 and ‘j’ represent the column.

Output

Java Pascal Triangle Program output

The time complexity of the above program is O(n^2) and space complexity – O(1).

If you have any doubts then comment below.

Leave a Reply

Close Menu