Home » Interview Questions » Dynamic Programming Interview Questions » Pascal Triangle Leetcode

Pascal Triangle Leetcode


()

The Pascal Triangle is a very good Leetcode problem that is asked so many times in Amazon, Microsoft, and other companies. we have given non-negative integer rows, print first rows rows of the pascal triangle.

Example

rows = 5

Pascal Triangle Leetcode

rows = 6

Pascal Triangle Leetcode

Types of solution for Pascal Triangle Leetcode

  1. Dynamic Programming

Dynamic Programming

Approach

The idea is to understand that if we have a row of pascal triangle, we can easily calculate the next row by iteratively adding adjacent values of the current row. This iterative process of generating a pascal triangle has been considered to be a dynamic programming approach wherein we construct each row based on the previous row.

Algorithm for Pascal Triangle Leetcode

  1. define base cases.
  2. Initialize the first row of the pascal triangle as {1}.
  3. Run an outer loop from i = 0 to i = rows, for generating each row of the triangle.
  4. Run an inner loop from j = 1 to j = {previous row size} for calculating element of each row of the triangle.
  5. in the inner loop, while calculating the elements of a row, add each pair of adjacent elements of the previous row in each step of the inner loop.
  6. After the inner loop gets over, simply output the row generated.
  7. Perform the outer loop for the number of rows given and subsequently print each row of the pascal triangle.

The algorithm is depicted below:

READ  Ugly Numbers

Pascal Triangle Leetcode

Implementation

C++ Program for Pascal Triangle Leetcode
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void pascalTriangle(int rows)
{
    if(rows == 0)
    return;
    
    vector <int> rowVector;
    
    for(int i=0;i<rows;i++)
    {
        rowVector.insert(rowVector.begin(),1);
        
        for(int j=1;j<rowVector.size() - 1 ;j++)
        rowVector[j] = rowVector[j]+rowVector[j+1];
        
        for(auto i : rowVector)
        cout<<i<<" ";
        
        cout<<endl;
    }
}
int main()
{
    int rows = 5;
    
    cout<<"The pascal triangle of "<<rows<<" rows is"<<endl;
    pascalTriangle(rows);
    
    
    return 0;
}
The pascal triangle of 5 rows is
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
Java Program for Pascal Triangle Leetcode
import java.io.*;
import java.util.*;

class TutorialCup
{
    static void pascalTriangle(int rows)
    {
        if(rows == 0)
        return;
        
        ArrayList <Integer> rowVector = new ArrayList<>();
        
        for(int i=0;i<rows;i++)
        {
            rowVector.add(0,1);
            
            for(int j=1;j<rowVector.size() - 1 ;j++)
            rowVector.set(j,rowVector.get(j)+rowVector.get(j+1));
            
            Iterator it = rowVector.iterator();
            
            while(it.hasNext())
                System.out.print((Integer)it.next()+" ");
            
            System.out.println();
        }
    }
    public static void main (String[] args) 
    {
        int rows = 5;
    
        System.out.println("The pascal triangle of "+rows+" rows is");
        pascalTriangle(rows);
    }
}
The pascal triangle of 5 rows is
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1

Complexity Analysis

  1. Time complexity: T(n) = O(rows2), two nested loops.
  2. Space complexity: A(n) = O(rows2), for storing each of the rows of the pascal triangle.

References

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions