Pascals Triangle Problem

Pascal’s triangle is a triangular array of the binomial coefficients. Write a function that takes an integer value n as

input and returns a two-dimensional array representing pascal’s triangle.

pascalTriangleArray is a two-dimensional array of size n*n, where

pascalTriangleArray[i][j] = BinomialCoefficient(i, j); if j

pascalTriangleArray[i][j] = 0; if j>i

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

Example One

Input: 4

Output:

1

1 1

1 2 1

1 3 3 1

Pascal’s Triangle for given n=4:

Using equation,

pascalTriangleArray[i][j] = BinomialCoefficient(i, j); if j

pascalTriangleArray[i][j] = 0; if j>i

Generated pascal’s triangle will be:

1

1 1

1 2 1

1 3 3 1

Example Two

Input: 6

Output:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

Pascal’s Triangle for given n=6:

Using equation,

pascalTriangleArray[i][j] = BinomialCoefficient(i, j); if j

pascalTriangleArray[i][j] = 0; if j>i

Generated pascal’s triangle will be:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

Notes

Input Parameters: There is only one argument n, denoting the number of lines of Pascal’s triangle to be considered.

Output: Return a two-dimensional integer array result, denoting pascal’s triangle where each value must be modulo with (10^9 + 7). Size of result[i] for 0 <= i=”” <=”” n=”” should=”” be=”” (i=”” +=”” 1)=”” i.e.=”” 0s=”” for=”” pascaltrianglearray[i][j]=”0;” if=”” j=””>i, should be ignored.</=>

Constraints:

• 1

Solutions

We provided two solutions.

1) brute_force_solution.java

A naive approach would be to calculate each (binomial coefficient % mod) separately. Binomial coefficient nCr = n!/((n-r)! * r!). So, calculate numerator = (n! % mod) , denominator = (((n-r)! * r!) % mod). Finally nCr can be found as ((numerator * moduloInverse(denominator)) % mod).

Time Complexity:

O(n^3) where n is the given number.

As there are n rows and each row can have n element in worst  cases. For calculating nCr for each element it will take O(n). Hence for n*n elements it will take O(n^3).

Auxiliary Space Used:

O(1).

As we are not storing anything extra. (Here we are ignoring space used to store output 2d array result which will be O(n*n))

Space Complexity:

O(n * n).

As input is O(1), auxiliary space used is O(1) and output space is O(n * n).

2) optimal_solution.java

As we know, for Pascal’s triangle pascalsTriangle[i][j] = pascalsTriangle[i-1][j] + pascalsTriangle[i-1][j-1] and pascalsTrianlge[i][0] = 1 and pascalsTriangle[i][i]=1. For 0

We use these facts and iterate each row and find out the pascalsTriangle.

Time Complexity:

O(n^2) where n is the given number.

As there are n rows and each row can have n element in worst  cases so, to iterate over n*n elements it will take O(n^2).

Auxiliary Space Used:

O(1).

As we are not storing anything extra. (Here we are ignoring space used to store output 2d array result which will be O(n*n))

Space Complexity:

O(n * n).

As input is O(1), auxiliary space used is O(1) and output space is O(n * n).