Home » Technical 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  Add and Search Word - Data structure design LeetCode

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup