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<=i,

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

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<=i,

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

Generated pascal’s triangle will be:

1

1 1

1 2 1

1 3 3 1

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<=i,

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

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.

• 1 <= n <= 1700

**Solutions**

We provided two solutions.

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).

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<=i<n and 0<=j<=i.

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).