You are given an integer ‘N’. You need to return the first ‘N’ rows of Pascal’s triangle.
Example:
Input:
N = 4
Output:
1
1 1
1 2 1
1 3 3 1
Explanation: The output matrix has the first four rows of Pascal’s Triangle.
The first line of the input will contain an integer ‘N’.
Print the first ‘N’ rows of Pascal’s Triangle.
You don’t need to print anything. Just implement the given function.
1 <= N <= 30
Time Limit: 1 sec
5
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Input:
N = 5
Output:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Explanation: The output matrix has the first five rows of Pascal’s Triangle.
3
1
1 1
1 2 1
4
1
1 1
1 2 1
1 3 3 1
Think of the pattern as a 2-D matrix.
Approach:
Algorithm:
Function [int][int] pascalTriangle(int N):
O( N*N ), Where ‘N’ is the given input.
We use two nested loops of O(N) and O(N), respectively. Hence, the overall complexity will be O( N*N ).
O( 1 ).
We are taking O( 1 ) extra space for elements. Hence, the overall complexity will be O( 1 ).
All tags
Sort by
Interview problems
beats 99.94% || Java solution || easy solution
public static int[][] pascalTriangle(int N) {
// Write your code here.
int arr[][] = new int[N][N];
for(int i=0 ;i<N; i++){
int ar[] = new int[i+1];
for(int j=0 ;j<=i; j++){
if(j==0 || j==i){
ar[j] = 1;
}else{
ar[j] = arr[i-1][j-1]+arr[i-1][j];
}
}
arr[i] = ar;
}
return arr;
}
Interview problems
this is a python solution that beats 97-100%.
from typing import *
def generate(row):
ans=1
ansrow=[1]
for col in range(1,row):
ans*=(row-col)
ans//=col
ansrow.append(ans)
return ansrow
def pascalTriangle(n : int) -> List[List[int]]:
ans=[]
for row in range(1, n+1):
ans.append(generate(row))
return ans
Interview problems
Optimal Solution In C++ 🔥🔥
#include<bits/stdc++.h>
using namespace std;
vector<int> generateRow(int row){
long long ans = 1;
vector<int> ansRow;
ansRow.push_back(1); // 1st element is 1
for(int i = 1 ; i < row ; i++){
ans = ans * (row-i);
ans = ans/(i);
ansRow.push_back(ans);
}
return ansRow;
}
vector<vector<int>> pascalTriangle(int N) {
// Write your code here.
vector<vector<int>> ans;
for(int i=1;i<=N;i++){
ans.push_back(generateRow(i));
}
return ans;
}
Interview problems
Easy?
Woah okay they levelled it as an “Easy” question apparently
Interview problems
striver approach
vector<int>generaterow(int row){
long long ans=1;
vector<int>ansrow;
ansrow.push_back(1);
for(int col=1;col<row;col++){
ans=ans*(row-col);
ans=ans/(col);
ansrow.push_back(ans);
}
return ansrow;
}
vector<vector<int>> pascalTriangle(int N) {
vector<vector<int>>ans;
for(int i=1;i<=N;i++){
ans.push_back(generaterow(i));
}
return ans;
}
Interview problems
Print Pascal’s Triangle
vector<vector<int>> pascalTriangle(int N) {
// Write your code here.
vector<vector<int>>ans;
ans.push_back({1});
ans.push_back({1,1});
for(int i = 2;i<N;i++){
vector<int>temp;
temp.push_back(1);
for(int j = 1;j< ans[i-1].size();j++){
temp.push_back(ans[i-1][j-1]+ans[i-1][j]);
}
temp.push_back(1);
ans.push_back(temp);
}
return ans;
}
Interview problems
JAVA->EASY
import java.util.*;
public class Solution {
public static int[] generate(int n) {
int[]arr=new int[n];
long ans=1;
arr[0]=1;
for(int i=1;i<n;i++){
ans=ans*(n-i);
ans=ans/i;
arr[i]=(int)ans;
}
return arr;
}
public static int[][] pascalTriangle(int N) {
int[][]res=new int[N][N];
for(int i=0;i<N;i++){
res[i]=generate(i+1);
}
return res;
}
}
Interview problems
By generating rows we can easily print pascal triangle .
// this function takes a row number and gives the entire row
vector<int> generaterow(int row ){
long long ans = 1;
vector<int>Ansrow;
Ansrow.push_back(1);
for(int col = 1; col<row ; col++){
ans = ans *(row-col);
ans = ans/col;
Ansrow.push_back(ans);
}
return Ansrow;
}
// to print the whole pascal triangle
vector<vector<int>> pascalTriangle(int N) {
// Write your code here.
vector<vector<int>> ans;
for(int i =1 ;i<=N ;i++){
vector<int> temp = generaterow(i);
ans.push_back(temp);
}
return ans;
Interview problems
Beginner Friendly Solution
vector<int> generateRow(int row){
long long ans =1;
vector<int> ansRow;
ansRow.push_back(1);
for(int col =1;col<row;col++){
ans = ans *(row - col);
ans = ans / (col);
ansRow.push_back(ans);
}
return ansRow;
}
vector<vector<int>> pascalTriangle(int N) {
// Write your code here.
vector<vector<int>> ans;
for(int i =1;i<=N;i++){
ans.push_back(generateRow(i));
}
return ans ;
}
Interview problems
Simplest CPP Solution|Easy To understand
vector<vector<int>> pascalTriangle(int n) {
// Write your code here
vector<vector<int>> nums;
for(int i=0;i<n;i++)
{
vector<int> d(i+1,0);
for(int j=0;j<=i;j++)
{
if(j==0||j==i)
{
d[j]=1;
}
else
{
d[j]=nums[i-1][j]+nums[i-1][j-1];
}
}
nums.push_back(d);
}
return nums;
}
