Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Pascal's Triangle

Easy
0/40
Average time to solve is 20m
369 upvotes
Asked in companies
GoogleJP MorganTata Consultancy Services (TCS)

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
3
1
2
3
Sample Output 1 :
1
1 
1 1 
1 
1 1 
1 2 1 
Explanation of The Sample Input 1:
For the first test case:
The given integer N = 1 you have to print the triangle till row 1 so you just have to output 1.

For the second test case:
The given integer N = 2 you have to print the triangle till row 2 so you have to output 
1
1 1

For the third test case
The given integer N = 3 you have to print the triangle till row 3 so you have to output 
1
1 1
1 2 1
Sample Input 2 :
3
4
5
6
Sample Output 2 :
1 
1 1 
1 2 1
1 3 3 1 
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1
1 5 10 10 5 1
Hint

Try to think about how you get the values of coefficients recursively.

Approaches (3)
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<N.
  • 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.
Time Complexity

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

Space Complexity

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.

Code Solution
(100% EXP penalty)
Pascal's Triangle
All tags
Sort by
Search icon

Interview problems

"Pascal's Triangle" pattern

#include <bits/stdc++.h>

 

vector<vector<long long int>> printPascal(int n) 

{

  // Write your code here.

  vector<vector<long long int>> v(n);

  for(int i=0; i<n; i++){

    v[i].resize(i+1);

    for(int j=0; j<i+1; j++){

      if(j==0 || j==i) v[i][j]=1;

      else v[i][j] = v[i-1][j-1] + v[i-1][j];

    }

  }

  return v;

}

 

89 views
0 replies
1 upvote

Interview problems

EASY and BEST SOLUTION C++

#include <bits/stdc++.h>

vector<long long int>generateRow(int row){

  vector<long long int>arr;

  long long ans =1;

  arr.push_back(1);

  for(int col=1;col<row;col++ ){

    ans =ans*(row-col);

    ans = ans/col;

    arr.push_back(ans);

  }

  return arr;

}

vector<vector<long long int>> printPascal(int n) 

{

  vector<vector<long long int>>ans;

  for(int i=1;i<=n;i++){

    ans.push_back(generateRow(i));

  }

  return ans;

}

 

158 views
0 replies
1 upvote

Interview problems

Pascal's Triangle c++

#include <bits/stdc++.h>

 

vector<vector<long long int>> printPascal(int n) 

{

  

    vector<vector<long long int>>ans(n);

 

    for(int i=0; i<n; i++){

        ans[i].resize(i+1);

 

        for(int j=0; j<i+1; j++){

          

          if(j==0 || j==i){

            ans[i][j] = 1;

          }

 

          else{

 

            ans[i][j] = ans[i-1][j] + ans[i-1][j-1];

          }

          

 

        }

    }

 

    return ans;

 

}

 

180 views
0 replies
0 upvotes

Interview problems

Pascals Triangle(optimized solution)

vector<long long >generate(int row){

    long long ans=1;

    vector<long long>ansRow;

    ansRow.push_back(1);

 

    //calculating entire row 

    for(int col=1; col<row;col++){

        ans=ans*(row-col);

        ans=ans/col;

        ansRow.push_back(ans);

    }

    return ansRow;

}

 

vector<vector<long long int>> printPascal(int n) {

  // Write your code here.

  vector<vector<long long int>>ans;

  for(int row=1;row<=n;row++){

      ans.push_back(generate(row));

  }

  return ans;

 

}

161 views
0 replies
0 upvotes

Interview problems

Java Solution - Space Complexity - O(1) -Easy

  1. Try to paste it in a notepad and check the steps
  2. First we need to create an ArrayList of the same type that we are gonna return 
  3. So, we need to add list in each index of ArrayList
  4. For 0th index, 1 element
  5. For 1st index, 2 elements
  6. For 2nd index,3 elements
  7. So traverse from 0 to n 
  8. inside the for loop another for loop from 0 to i(inclusive)
  9. Because for Oth row, it should iterate 1 time only , Therefore for(int j=0;j<=i;j++)
  10. then we can see the first index and last index should be 1 so added 1 if j==0 or j==1 
  11. Then in case the index is neither the last index or first index
  12. We implemented the logic as in the Pascal Triangle we can see
  13. The current list index is the sum of the previous list currentindex-1 and currentindex, in this code i.e. j-1 and j as j is the index where we are adding the elements

public class Solution {

    public static ArrayList<ArrayList<Long>> printPascal(int n) {

        ArrayList<ArrayList<Long>> result = new ArrayList<>();

        for(int i=0;i<n;i++){

            result.add(new ArrayList<>());

            for(int j=0;j<=i;j++){

                if(j==0 || j==i) // as all the first and last index of list is 1

                    result.get(i).add((long)1);

                else //in case the index is neither the last or first index

                    result.get(i).add(result.get(i-1).get(j-1) + result.get(i-1).get(j));

            }

        }

        return result;

    }

}

 

133 views
0 replies
0 upvotes

Interview problems

Java Solution Using Lists - Simple Solution

public static ArrayList<ArrayList<Long>> printPascal(int n) {

            ArrayList<ArrayList<Long>> resultList = new ArrayList<>();

            if (n == 0) return resultList;

 

            ArrayList<Long> row = new ArrayList<>();

            row.add((long)1);

            resultList.add(row);

 

            ArrayList<Long> prevRow = new ArrayList<>();

            prevRow = row;

            for (int i = 1; i < n; i++) {

                ArrayList<Long> currentRow = new ArrayList<>();

                currentRow.add((long)1);

                for (int j = 1; j < i; j++) {

                    currentRow.add(prevRow.get(j) + prevRow.get(j - 1));

                }

                currentRow.add((long)1);

                resultList.add(currentRow);

                prevRow = currentRow;

            }

            return resultList;

    }

68 views
0 replies
0 upvotes

Interview problems

Python 10/11 but don't know what is wrong with last testcase

def printPascal(n:int):
    # Write your code here.
    # Return a list of lists.
    if n<2:
        return [[1]]
    if n<=5:
        res = []
        val = 1
        for i in range(1,n+1): 
            res.append(list(str(val)))
            val = 11*val
        return res
    res = []
    val = 1
    for i in range(1,5+1): 
        res.append(list(str(val)))
        val = 11*val
    for i in range(n-5):
        temp = [1]
        for j in range(len(res[-1])-1):
            temp.append(str(int(res[-1][j])+int(res[-1][j+1])))
        res.append(temp+[1])
    
    return res
116 views
1 reply
0 upvotes

Interview problems

@C++ easiest solution

vector<vector<long long int>> printPascal(int n) 

{

  // Write your code here.

  vector<vector<long long int>> ans;

  vector<long long > p;

  p.push_back(1);

  ans.push_back(p);

  if(n==1) return ans;

 

  p.push_back(1);

  ans.push_back(p);

  if(n==2) return ans;

 

  for(int i=3;i<=n;i++)

  {

    vector<long long int> temp;

    temp.push_back(1);

    for(int j=1;j<i-1;j++){

      temp.push_back(ans[i-2][j-1]+ans[i-2][j]);

    }

    temp.push_back(1);

    ans.push_back(temp);

  }

  return ans;

 

}

504 views
0 replies
1 upvote

Interview problems

Easy Python Solution Using Binomial Theorem

Python Solution j - Be sure to remove all the imports

Time Complexity - O(N^2)

 

def kthRow(n):
    lst = []
    if n == 0:
        return lst
    lst.append(1)
    res = 1
    for i in range(1,n):
        res = res * (n-i)
        res = (res// i)
        lst.append(res)
    return lst

def printPascal(numRows:int):
    lst = []
    for i in range(1,numRows+1):
        lst.append(kthRow(i))
    return lst
171 views
0 replies
2 upvotes

Interview problems

C++ easy solution

#include <bits/stdc++.h>

vector<long long int> solve(int rows)

{

   vector<long long int>ds;

   long long temp=1;

   ds.push_back(1);

   for(int i=1;i<rows;i++)

   {

      temp*=(rows-i);

      temp/=i;

      ds.push_back(temp);

   }

   return ds;

}

vector<vector<long long int>> printPascal(int n) 

{

  vector<vector<long long int>>ans;

  for(int i=1;i<=n;i++)

    ans.push_back(solve(i));

 

  return ans;

}

 

programming

451 views
0 replies
0 upvotes
Full screen
Console