Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

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

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

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

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

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

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

Note: Input and Output will already be taken care of.