Pascal Triangle | Finding nCr in minimal time

Problem Link: bit.ly/3jY4iuF
Notes/C++/Java/Python codes: takeuforward.o...
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/take...
00:51 What do you mean by Pascal's Triangle?
02:27 3 Types of problems that might be asked to you
03:52 1st Type Problem Statement
06:56 Formula shortcut
07:49 Code
09:46 Complexity
10:31 recap
10:54 2nd Type Problem Statement
11:38 Brute force
12:18 Complexity
12:37 Optimal solution & Deep dive into formula and observation
15:11 Minor changes and formula
17:27 Pseudocode
19:06 Complexity
19:21 3rd Type Problem Statement
20:00 Brute force
20:07 Pseudocode
21:17 Complexity
21:50 Optimal Solution
22:19 Code
25:16 Interview Tip : Code Quality

[@takeUforward]

Please watch our new video on the same topic: kzbin.info/www/bejne/mIOanoSdrLaSpZo

[@arpitbhavsar6020]

Recursion without a base case 😁😁

[@KurumiddeKezia]

Bro one dout my code is executed in codestudio but not executed in leetcode y😢

[@the_avii_7]

@@arpitbhavsar6020 🤣🤣

[@takeUforward]

Please do like the video, it won't cost you anything, but it will highly motivate me :)

[@shra1]

Did this problem move to easy from hard?

[@ankushprajapati519]

Ofcourse we do...... But not only for motivation,but also for your efforts.......😊 Such type of free content is very helpful for those persons who are not capable to buy an expensive course......👍✨

[@newsbuster2194]

done bhaiya

[@divyareddy7622]

your videos actually got me out of depression and gave me aa hope at becoming better at DSA!!!!

[@chandan1s2]

got better?

[@shashankgsharma0901]

What's the status now champ?

[@codewithtejaswi]

What's the update on your depression champ🎉

[@hellsterkun8764]

lol

[@TasneemMohammad-oj3ie]

lol update bro?

[@swacharahman5084]

I always amazed the level of intelligence you have brother, Thank you for this playlist, Trust me your playlist is making thousands/millions of students better coder.

[@p1xel3434]

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

[@chiraggill2940]

will not affect complexity though so no need

[@arshkumar5928]

Maybe you wanted to say min(r, n-r ), because this will reduce the no. of operations when r > n-r

[@ashutoshsahu5567]

Frankly speaking I am not able to understand Pascal triangle problem until I watched this video, Earlier I see almost 5-7 videos on KZbin , from those videos I Get what is the pascal triangle, but didn't able to solve the problem. After watching this video, I have confidence to solve any problem based on pascal triangle.

[@akashkumarmaurya2319]

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

[@naveensaicremsiyadlapalli3769]

#include using namespace std; class PascalsTriangle{ private: int Ncr(int n,int r) { int ans=1; for(int i=1;i

[@Limitless_Sky_Codes]

dammmm, man the level of observation ...want to really know first time in college how u solved these at that time ..at that present time how u approached to this problem..?full explanation and feeling ,... story...

[@priy9491]

We can reduce the time complexity to (n^2/2) by running the inner loop only for row/2 times and assigning values symmetrically because the pascals triangle is symmetric. Thank you for the videos!

[@RajNamdev_19]

that's what I was thinking

[@Gurunat16]

To add symmetry to the result, you need to run a loop right? Or is there any other ways?

[@priyankasoni5537]

Can you please explain Space complexity of both the approaches of variation 3? Like how come it is O(1)(Written in the sheets notes and also strivers mentioned in the video

[@AnkitKumar-su1yi]

@@priyankasoni5537 yes its O(1) because we are not using any extra space like we are asked to print the pascals triangle so we are just using a list to store and print it that's it

[@priyankasoni5537]

@@AnkitKumar-su1yi thank u understood

[@chethanprabhu4475]

Finally I was able to solve a problem before looking at your solution. That too hard one 😎 All thanks to your foundational videos on Arrays ♥ Watched the video anyways. Just to look at your approach

[@cinime]

Understood! Super awesome explanation as always, thank you very very much for your effort!!

[@mirishfaqhussain6168]

His involvement while he delivers the lecture is motivational ❤

[@ishanraghuvanshi3283]

I just did a[ i ][ j ]= a[ i-1 ][ j-1 ] + a[ i-1][ j ] keeping first and last element of the arrays 1, takes O(n^2) compexity but works fine

[@sarthakjain1824]

450 questions will need many months of continuous hard work. Hats off bhaiya

[@takeUforward]

We have already covered > 60%, trees : 56, graphs: 56 dp: 56 ;)

[@AdityaSingh-in6ce]

there is no good playlist for string on KZbin only one or two videos and its and important topic please start with string@@takeUforward

[@amansayyad7286]

i think best teacher present is this man. Please try to motivate him and support him. Love you bro

[@HansrajSinghShekhawat-s3u]

I computed it using memoization. I didn't think of the combinations formula whilst coding it. The video was very helpful. Thanks!!

[@parasarora5869]

That was fabulous. I didn't know about nCr unfortunately, but I learned it separately from other videos. Thanks for the great video. ❤

[@md.ualiurrahmanrahat2400]

used to solve this problem by myself but the solution was brute force method. Never have I ever thought this problem can be solved by such observation. Hats off to the effort Striver puts in his video. Incredible!

[@AshutoshVerma-d4z]

instead, for the first problem, the loop should run for min(r, n-r) and not 'r' because if it is 10C7, r is bigger than n-r

[@harshsinha7642]

I tried solving ncr problem with this approach but still test cases are failing for ex 69c43 You can search ncr problem gfg ... Can you try solving with first approach along with min(n-r, r) modification and let me know?

[@NikitaSingh-kz2ii]

APPROACH TO THIS PROBLEM IS SUPER SE V BHT BHT BHT ZYADA UPAR🔥🔥🔥🔥🔥🔥🔥🔥🔥

[@deokumarjnu]

Thanks Striver, my code is not passing because of spacing issue in between digits😌 we can do in more way, pascle is nothing but power of 11, so if it's asking for N, then just run a loop from 1 to N and calculate the power(11, i), push into the vector if spacing is not considered. Stuck with spacing.

[@infinitecodes]

Thank you very much for this amazing course 🎉❤

[@RaunitJaiswal-s9v]

- [00:02](kzbin.info/www/bejne/mIOanoSdrLaSpZo) 🧠 Overview of the DS Algo course and problem statement of Pascal's triangle - The course is extensive and covers over 400 problems in DS algo - Introduction to Pascal's triangle and its structure - Explanation of three types of problems related to Pascal's triangle - [03:53](kzbin.info/www/bejne/mIOanoSdrLaSpZo) 🧮 Calculating nCr using brute force method - Discussing the traditional brute force method to calculate nCr - Explaining the formula for nCr and line-by-line code implementation for nCr calculation - Detailed explanation of time complexity considerations and space complexity - [10:55](kzbin.info/www/bejne/mIOanoSdrLaSpZo) 🖨 Optimizing the calculation of nth row of Pascal's triangle - Introducing the optimization to calculate the nth row more efficiently - Deriving a formula based on observations to calculate elements of the nth row - Implementing the optimized code for generating and printing the nth row - [19:30](kzbin.info/www/bejne/mIOanoSdrLaSpZo) 🪙 Generating the entire Pascal's triangle efficiently - Explaining a naive brute force approach to generate the entire Pascal's triangle - Describing a more optimized method using the second type of problem solution - Discussing the time complexity reduction strategy for generating the complete Pascal's triangle with improved efficiency - [22:02](kzbin.info/www/bejne/mIOanoSdrLaSpZo) 🧮 Solution complexity analysis - Optimal time complexity for type 3 problem is O(n^2) - Generating each row has a time complexity of O(n) - Using long long data type is recommended due to potential large number calculations - [24:24](kzbin.info/www/bejne/mIOanoSdrLaSpZo) 📝 Coding the solution - Write a function to generate a row based on the row number - Use the function to generate the entire triangle structure - Code quality is important in interviews, focus on readability and structure - [26:04](kzbin.info/www/bejne/mIOanoSdrLaSpZo) 📚 Final notes and channel engagement - Encouragement to like the video to support content creation - Importance of subscribing for more content - Follow links in the description for further engagement on social media platforms

[@depthsoffacts3651]

🔥🔥 love your teaching 🤗 you are my inspiration

[@prabhatkumarsingh3073]

3:40 4th type question can be asked is sum of nth row ans :simple left lift 1 by (n-1) that is 1

[@ChanduThota-z7t]

very very nice explaination anna

[@habeeblaimusa4466]

Your explanation is superb ❤️❤️.. Ride on Striver.

[@priyotoshsahaThePowerOf23]

Thanks for taking us forward,, Striver❤

[@prajwalnakure]

00:04 Pascal's Triangle - A pattern of numbers where each number is the sum of the two directly above it. 02:05 Finding element at a specific row and column in Pascal Triangle. 06:48 Shortcut for finding nCr in minimal time: multiply numbers from n to n-r+1. 09:11 The numerator in nCr calculation keeps getting multiplied and then divided with the value of i+1. 13:39 Pascal Triangle formula is used to find nCr in minimal time. 15:59 Pascal Triangle for finding nCr 20:22 Generate Pascal Triangle row in minimal time 22:16 Optimal solution for finding nCr in minimal time 26:16 The KZbinr encourages viewers to subscribe and engage with their content.

[@suyashshinde2971]

SDE Sheet: Day 1 Problem 2 Done!

[@sathvikreddy4807]

so how many have you done till now>?

[@Manishgupta200]

It's a very tricky problem based of math nCr.. approach by you is really good

[@artitech6668]

Amazing explanation. thanks a ton. Working harder to make u proud.

[@aakarshshukla8364]

congrats striver for 700k and happy Diwali🎆🎆🎇🎇🧨🧨

[@souvikbiswas292]

You are the GOD of dsa

[@venup2813]

Excellent 👌

[@bharathis7890]

verrry good explanation and even the methods of solving the given problem😇

[@bilalahmedkhan5876]

Loved it, very well explained!

[@ARYANGUPTARA]

Python code for 1st variant def pascal(n,r): res = 1 for i in range(r): res = res * (n-i) res = res/(i+1) print(res) n = int(input("Value of N")) r = int(input("Value of R")) pascal(n-1,r-1)

[@rahuljmd]

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

[@jatinsareen7771]

Hey striver, I was having a doubt that will you cover up some competitive programming concepts in this course or not?? Because covering all cp topics will make this course legendary and no one will be able to surpass this level in generations.

[@Bababahahabwhwh]

😂😂😂lol

[@shaktijain8560]

Each row is binomial expansion coefficient for certain power. We can directly use combination formula to get it .

[@sukhpreetsingh5200]

Awesome explanation as usual💗

[@Mohit-s9c2v]

understood, Thankyou Striver

[@nice_random_guy5347]

Understood! Thanks

[@PogalaHarshitha]

thank you striver

[@poojakumarisingh5506]

Awesome video. Thankyou striver ❤❤

[@sainallajarla7022]

UNDERSTOODDDD STRIVER !!!

[@psrs985]

Or you could use the previously stored values to generate the lower rows which will take O(n*n) TC

[@sourabhsoni5065]

Very Nice Explanation

[@arnavjain6038]

class Solution(object): def pascal(self, numRows): pt=[[1]]*(numRows) pt[0]=[1] for i in range(1,numRows): pt[i]=[1]*(i+1) for j in range(1,i): pt[i][j] = pt[i-1][j-1]+pt[i-1][j] return pt for generating entire pascal's triangle.

[@kj5215]

1st -> 3:51 2nd -> 10:55 3rd -> 19:21

[@akshatmalviya8563]

I did the last part with dp. Complexity was O(n^2)

[@shrutisrivastava7174]

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

[@culeforever5408]

understood 😇

[@anitha8562]

Striver!!Please upload videos on binary search.

[@AjeyaKumaraK]

superb explanation

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@ishaanrejra1084]

You are the best !

[@torishi82]

Samaj aa gaya!!

[@shanks5719]

Understood, sir.

[@mainakdasgupta7130]

Thank you

[@inspiringzone12]

Excellent👍👏

[@complexcat6329]

understood, thank you!

[@rishabhgupta1222]

Understood very well

[@Limitless_Sky_Codes]

understood ....but not got that row-1 and col -1 on own when was trying.....

[@Shivi32590]

understood. Respect!

[@shivamjain1811]

whats the intiution behind (n-1)C(r-1) ? can someone plz tell

[@adirohilla]

I am also looking for its intuition, thanks for raising this , but nobody has still answered on it yet

[@tarunrajput6865]

12:43 yaha se dekh Bhai agr phir bhi na smjh aye TB btayio

[@prerakhere]

Look at this step by step: The rows and columns of Pascal's triangle starts from r=0 and c=0. r=0, c=0: What are the number of ways to choose 0 items from 0 items = 1 r=1, c=0: What are the number of ways to choose 0 items from 1 item = 1 r=1, c=1: What are the number of ways to choose 1 item from 1 item = 1 r=2, c=0: What are the number of ways to choose 0 item from 2 items = 1 r=2, c=1: What are the number of ways to choose 1 item from 2 items = 2 r=2, c=2: What are the number of ways to choose 2 items from 2 items = 1 r=3, c=0: What are the number of ways to choose 0 items from 3 items = 1 r=3, c=1: What are the number of ways to choose 1 item from 3 items = 3 r=3, c=2: What are the number of ways to choose 2 items from 3 items = 3 r=3, c=3: What are the number of ways to choose 3 items from 3 items = 1 ... goes like this i got this intuition from wiki: en.wikipedia.org/wiki/Pascal%27s_triangle

[@reddygopichand2002]

We can use ncr=nc(n-r) when r>n/2 10:44

[@NazeerBashaShaik]

Understood, thank you.

[@heyOrca2711]

Understood! sir

[@AshishSahu-ef9rl]

Maja aagaya 😊

[@yamini436]

understood :) thankyou striver

[@vigneshkumarganesan1529]

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?

[@vanamadinarendra2974]

Keep doing great 👍🎉

[@SumitMishra-rb8zo]

For Part 1- 3:51 to 10:52, part 2- 10:56 to 19:14

[@ashishpradhan6250]

understood ..Thanks🙂

[@nishant4595]

understood!!

[@YourCodeVerse]

Understood✅🔥🔥

[@konankikeerthi]

Thanks bro. Understood

[@thebestofyoutube4810]

Thanks a lot my ninja.....

[@heyanikethere]

Great work....

[@Shakti_singh96]

00:04 Pascal's Triangle - A pattern of numbers where each number is the sum of the two directly above it. 02:05 Finding element at a specific row and column in Pascal Triangle. 06:48 Shortcut for finding nCr in minimal time: multiply numbers from n to n-r+1. 09:11 The numerator in nCr calculation keeps getting multiplied and then divided with the value of i+1. 13:39 Pascal Triangle formula is used to find nCr in minimal time. 15:59 Pascal Triangle for finding nCr 20:22 Generate Pascal Triangle row in minimal time 22:16 Optimal solution for finding nCr in minimal time 26:16 The KZbinr encourages viewers to subscribe and engage with their content. Crafted by jai rajputana

[@codeman3828]

Wonderful

[@akilesh6379]

understood sir

[@HustlingCoders]

Understood sir

[@hxgaming8886]

good video ... understood

[@arnavsaha3631]

This is great...I hope you earn enough from all this 😊

[@anshulrai6058]

understood👍

[@trsk]

thank you Anna

[@gautamsaxena4647]

understood bhaiya

[@itsabhinav04]

Understood, thanks :)

[@AlokSingh-jw8fr]

int mod = 1000000007; int nCr(int n, int r){ if(n

[@chanderveersinghchauhan2778]

mila iska ans ??

[@vamsikrishnagannamaneni912]

7:22? I didnot understand part? 10/3 will give me nothing? what does that mean ? it will give 3.333 or 3 if rounded right?

[@her_soulmate]

Understood 🎉

[@hetpatel7399]

Aap 3rd year me the tab aap kitane hours Coding karate the??

[@yasaswiv2030]

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

[@iamaniket9]

understood 👌👌👌👌❤❤❤❤

[@meghnakhaitan2495]

Can you pls pls plsssss do strings before binary search next plsss🙏 ?

[@introvert9112k]

Just a small improvement for the nCr calculation. int findNumber(int n,int r) { long long res = 1; for(int i = n; i > max(r,n-r); --i) { res*=i; res/=(n-i+1); } return res; } Time Complexity : O( min(r, n-r) )