Pascal Triangle | Finding nCr in minimal time

🥰🥰😘😘

I don't get the point where he bring the formula. How did he arrive that formula will give the output? anyone knows the answer?

can we do it with that apprach as we have seen them as the square , cube and quadraple of 11 as 11,121,1331....and so on so we first convert that no . to string and then string to that vector and then print:)
this will take as overall complexity of O(N) in worst case

How about this? This is the 3rd type - print the entire triangle and I believe this is also O(n^2) solution (can someone please confirm?). I came up with this in Leetcode before watching the solution video.

class Solution {
public:
vector<vector<int>> generate(int numRows) {
std::vector<std::vector<int>> result;
result.reserve(numRows);
result.push_back({1});

for (int i = 0; i < numRows - 1; i++) {
std::vector <int> vals;
vals.reserve(i+1);
vals.push_back(1);
for (int j = 1; j < result[i].size(); j++) {
auto val = result[i][j-1] + result[i][j];
vals.push_back(val);
}
vals.push_back(1);
result.push_back(vals);
}
return result;
}
};

Understood!

Understood

we can use recursion right ??
generate the answer for N-1 and the add another row by with the help of last row of generated answer and add this row and return the final answer

Understood

understood

java soln?

Understood ❤

Really amazed by ur Intelligence but i don't know why i am not think this kind of solution on my own why 😭😭😭

Love it

Printing Pascal triangle using DP

vector<vector<int>> generate(int numRows) {
vector<int>firstRow { 1 };
vector<vector<int>> ans;
ans.push_back( firstRow );
for( int row = 2 ; row <= numRows; row++ )
{
vector<int> lastRow = ans.back();

vector<int> newRow;
newRow.push_back( 1 );

for( int i = 1; i <= row - 2; i++ )
{
newRow.push_back( lastRow[ i - 1] + lastRow[ i ] );
}
newRow.push_back( 1 );
ans.push_back( newRow );
}

understood

understood

understood, thank you!

public List<List<Integer>> generate(int numRows) {
List<List<Integer>> outer = new ArrayList<>();
int i = 0;

List<Integer> x = new ArrayList<Integer>();
x.add(1);
outer.add(x);

while(i < numRows - 1) {
List<Integer> inner = new ArrayList<Integer>();
inner.add(1);

List<Integer> last = outer.get(outer.size() - 1);

for(int j = 0; j <= last.size() - 2; j++) {
inner.add(last.get(j) + last.get(j+1));
}

inner.add(1);

outer.add(inner);
i++;
}
return outer;
}

What do you think about this solution? As i can see the complexity is O(r*c)?

understood

Understood✅🔥🔥

class Solution{
public:

vector<ll> generateRow(int row) {
long long ans = 1;
vector<ll> ansRow;
ansRow.push_back(1); //inserting the 1st element

//calculate the rest of the elements:
for (int col = 1; col < row; col++) {
ans = (ans * (row - col)));
ans = (ans / col));
ansRow.push_back(ans);
}
return ansRow;
}

vector<ll> nthRowOfPascalTriangle(int n) {
// code here
vector<vector<ll>> ans;

//store the entire pascal's triangle:
for (int row = 1; row <= n; row++) {
ans.push_back(generateRow(row));
}
return ans[n-1];
}
};

It is failing for n=74 for me. Don't know what is going wrong. Can someone please help

understood

Understood

understood 😇

understood

Thank you very much for this amazing course 🎉❤

understood

🎉

Understood

why didnt his code on screen not work and in notes there were 2 loops

Understood <3

Understood watching once more for being more clear

Thanks

Understood!

understood

Understood

Understood❤❤❤❤❤

very very easy solutoion ..every time i can think about only brute solution but u gived both the solution at same time which is fantastic ...amazing love the way you teach

Python Solution
from typing import *

def pascalTriangle(n : int) -> List[List[int]]:

def generateRow(row):
ans=1
ansRow=[]
ansRow.append(1)
for col in range (1, row):
ans=ans*(row-col)
ans=ans//col
ansRow.append(ans)
return ansRow

res=[[1]]
for i in range (2, n+1):
res.append(generateRow(i))
return res

Understood 🎉

class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> result = new ArrayList<>(numRows);

if(numRows ==0 ) return result;
for(int i = 0;i<numRows;i++){
List<Integer> row = new ArrayList<>(i+1);
for(int j = 0;j<=i;j++){
if (j == 0 || j == i) {
row.add(1);
} else if(i>1) {
List<Integer> prevRow = result.get(i - 1);
row.add(prevRow.get(j - 1) + prevRow.get(j));
}

}
result.add(row);

}
return result;
}
}

understood

Understood brother, Thanks for this amazing amazing explanation...

nCr = nC(n-r) so, we can take i < min(n, n - r) it is more efficient

Bhaiya, Combination wale question ki bhi list bana do please, Ya phir Combination ke concept ke baare mai ek acchi video bana do.