Pascal triangle
You are given an integer N. Your task is to return a 2-D ArrayList containing the pascal’s triangle till the row N.

A Pascal's triangle is a triangular array constructed by summing adjacent elements in preceding rows. Pascal's triangle contains the values of the binomial coefficient. For example in the figure below.

For example, given integer N= 4 then you have to print.

1 1 1 1 2 1 1 3 3 1 Here for the third row, you will see that the second element is the summation of the above two-row elements i.e. 2=1+1, and similarly for row three 3 = 1+2 and 3 = 1+2.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases. The first line of each test case contains a single integer N denoting the row till which you have to print the pascal’s triangle.

Output format :

For each test case, return the 2-D array/list containing the pascal’s triangle till the row N.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Pascal triangle

You are given an integer N. Your task is to return a 2-D ArrayList containing the pascal’s triangle till the row N.

A Pascal's triangle is a triangular array constructed by summing adjacent elements in preceding rows. Pascal's triangle contains the values of the binomial coefficient. For example in the figure below.

For example, given integer N= 4 then you have to print.

1  
1 1 
1 2 1 
1 3 3 1

Here for the third row, you will see that the second element is the summation of the above two-row elements i.e. 2=1+1, and similarly for row three 3 = 1+2 and 3 = 1+2.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains a single integer N denoting the row till which you have to print the pascal’s triangle.

Output format :

For each test case, return the 2-D array/list containing the pascal’s triangle till the row N.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 40
1 <= N <= 50

Time Limit: 1 sec

Accepted Answer

Recursive Solution

The idea is to use recursion to get the value of the coefficients we will create a helper function CALPASCAL which will take row and entry as its input parameters and we call this function in the main function of PRINTPASCAL.

Inside the function CALPASCAL if the row is 0 or the entry is equal to row then we will just return 1.
Else we will return the sum of adjacent previous row value that is CALPASCAL(I-1,J-1) + CALPASCAL(I-1,J).
Now for the main function to store the pascal’s triangle PRINTPASCAL inside this declare a 2-D arrayList TRIANGLE and run loop from row I=0 to I
Inside this loop run a loop from entry J=0 till entry J=R.
Inside this loop calculate the answer for each entry by calling the CALPASCAL function and add it to the arraylist.
Finally return the arraylist.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ denotes the number of Rows.

We need O(N) space to store all the values of a given row in a list. Also at worst case, our recursion will need O(N) stack space for the recursive call.

Time Complexity: O(2^n)Explanation:

O(2^N), Where ‘N’ denotes the number of Rows.

As we are calculating the coefficients every time in the row and the sum of coefficients for each row is 2^R where R is the row number and for all rows, it will give 2^N (by applying geometric progression).

Accepted Answer

Using previous rows to make new rows

The idea is to use the definition of pascal’s triangle that its coefficients and are summation of adjacent elements in preceding rows. so in this way we can store the elements in a matrix and for further generation of values in it we can check the preceding elements and update the value.

Declare an ArrayList of arraylist TRIANGLE to store the elements values.
Run a loop from row R =0 till N-1.
Now inside this loop run one more loop from value J=0 till J<=R.
If the number is first or last one then just store 1 in the matrix i.e. TRIANGLE[R][J]=1.
Else store the sum of adjacent elements in preceding rows i.e. TRIANGLE[R][J]=TRIANGLE[R-1][J-1] + TRIANGLE[R-1][J].
Print this value i.e. the value in the current iteration TRIANGLE[R][J].
Finally return the arrayList

Space Complexity: O(n^2)Explanation:

O(N^2), Where ‘N’ denotes the number of Rows.

We are using an ArrayList of ArrayList to store values.

Time Complexity: O(n^2)Explanation:

O(N^2), Where ‘N’ denotes the number of Rows.

because we are using two nested loops.

C++ (g++ 5.4)

/*
	Time Complexity: O(N^2)
	Space complexity: O(N^2)
	
	Where N denotes the number of Rows.
*/

#include

vector < vector < long long int >> printPascal(int n) {
    vector < vector < long long int >> triangle;
    vector < long long int > temp;

    temp.push_back(1);
    triangle.push_back(temp);
    for (int i = 1; i < n; i++) {
        temp.clear();
        for (int j = 0; j <= i; j++) {
            if (j == i || j == 0) {
                temp.push_back(1);
            } else {
                temp.push_back(triangle[i - 1][j - 1] + triangle[i - 1][j]);
            }
        }
        triangle.push_back(temp);
    }
    return triangle;
}

Java (SE 1.8)

/*
	Time Complexity: O(N^2)
	Space complexity: O(N^2)
	
	Where N denotes the number of Rows.
*/

import java.util.ArrayList;

public class Solution {
	public static ArrayList> printPascal(int n) {
		ArrayList> triangle = new ArrayList>();

		for (int row = 0; row < n; row++) {
			ArrayList add = new ArrayList();
			for (int i = 0; i <= row; i++) {
				if (row == i || i == 0) {
					add.add((long) 1);
				} else {
					add.add(triangle.get(row - 1).get(i - 1) + triangle.get(row - 1).get(i));
				}
			}
			triangle.add(add);
		}
		return triangle;
	}
}

Python (3.5)

'''
	Time Complexity: O(N^2)
	Space complexity: O(N^2)
	
	Where N denotes the number of Rows.
'''

def printPascal(n):
    
    triangle = []
    
    for row in range(n):
        
        add = []
        
        for i in range(row+1):
            
            if row == i or i == 0:
                
                add.append(1)
                
            else:
                
                add.append(triangle[row - 1][i - 1] + triangle[row - 1][i])
            
        triangle.append(add)
        
    return triangle

Accepted Answer

Using the property of coefficients.

The idea is to use the property of pascal’s triangle that its coefficients and are nothing but the binomial coefficients so we will calculate binomial coefficients of each line and at each index and print them, the coefficient value at every index is nCr where n is equal to the current row number and r is the rth entry in the row n and its value is FACT(n)/(FACT(n-r)*FACT(r)) where FACT(X) is the factorial of the number X but in this approach, we will use maths to derive the relation between Eth entry ‘RCE’ and (E-1)th entry RC(E-1)

So RCE and RC(E-1)
RCE = FACT(R)/(FACT(R-E)*FACT(E)) and RC(E-1)= FACT(R)/(FACT(R-E+1)*FACT(E-1)) after simplifying and comparing we get
RCE = RC(E-1) * (R-E+1)/E.
Declare an ArrayList of ArrayList TRIANGLE to store the values of the elements.
Now run a loop from row R=1 to R=N.
Inside this initialize RCE=1 that represents rCe.
Inside this loop run a loop from entry E=1 till entry E=R. Store RCE in the ArrayList and update RCE to RCE*(ROW - E)/E.
Finally, return ArrayList.

Space Complexity: O(1)Explanation:

O(1), We are using constant space.

Time Complexity: O(n^2)Explanation:

O(N^2), Where ‘N’ denotes the number of Rows.

because we are using two nested loops.

C++ (g++ 5.4)

/*
	Time Complexity: O(N^2)
	Space complexity: O(1)
	
	Where N denotes the number of Rows.
*/

#include

vector < vector < long long int >> printPascal(int n) {
    vector < vector < long long int >> triangle;
    vector < long long int > temp;

    for (int i = 1; i <= n; i++) {
        long long int rCe = 1;
        temp.clear();
        for (int j = 1; j <= i; j++) {
            temp.push_back(rCe);
            rCe = rCe * (i - j) / j;
        }

        triangle.push_back(temp);
    }
    return triangle;
}

Java (SE 1.8)

/*
	Time Complexity: O(N^2)
	Space complexity: O(1)
	
	Where N denotes the number of Rows.
*/

import java.util.ArrayList;

public class Solution {
	public static ArrayList> printPascal(int n) {
		ArrayList> triangle = new ArrayList>();

		for (int row = 1; row <= n; row++) {
			long rCe = 1;
			ArrayList add = new ArrayList();
			for (int i = 1; i <= row; i++) {

				add.add(rCe);
				rCe = rCe * (row - (long) i) / (long) i;
			}
			triangle.add(add);
		}
		return triangle;
	}
}

Python (3.5)

'''
	Time Complexity: O(N^2)
	Space complexity: O(1)
	
	Where N denotes the number of Rows.
'''

def printPascal(n):
    
    triangle = []
    
    for row in range(1, n+1):
        
        rCe = 1
        add = []
        
        for i in range(1, row+1):
            
            add.append(rCe)
            rCe = rCe * (row - i) // i
            
        triangle.append(add)
        
    return triangle

You are given an integer N. Your task is to return a 2-D ArrayList containing the pascal’s triangle till the row N.

A Pascal's triangle is a triangular array constructed by summing adjacent elements in preceding rows. Pascal's triangle contains the values of the binomial coefficient. For example in the figure below.

For example, given integer N= 4 then you have to print.

Input format :

Output format :

Note:

Constraints:

Top INCA INFOTECH TECHNOLOGIES Software Developer interview questions & answers

Popular interview questions of Software Developer