Unique Paths | Dynamic programming | Leetcode #62

This video explains an important dynamic programming interview problem which is to count all possible unique paths to reach from first cell to the last cell in a grid.We can solve this problem simply by using recursion but it is a costly process in terms of time.We can improve recursive solution by using a
lookup table which is called memoization.The most optimal approach is to solve using tabulation dynamic programming approach.I have shown the TOP-DOWN dynamic programming approach.I have explained the entire problem step by step by using proper examples and intuition for each step.I have dry run the algorithm and have also explained the code walk through at the end of the video.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
=================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
OTHER PROBLEMS:-
Dungeon Game: • Dungeon Game | Dynamic...
Coin change problem: • Coin Change 2 | Dynami...
Largest divisible subset: • Largest Divisible Subs...

[@saurabhsomani9188]

Somebody give this man a medal ASAP. Crystal clear explanations on each and every problem. Very Inspiring and Helpful.

[@techdose4u]

🤣 Hahahahaa.....Thanks for appreciating :D

[@VrickzGamer]

I like Your Dark theme in the videos which gives my eyes the power to view more.

[@thiyagarajanr225]

This man is so good at segementing the problems ! More power to you bro! A Die hard fan of you bro 💗

[@techdose4u]

Thanks :)

[@imshivendra]

I think TechDose Sir has joined Google. Congratulations.

[@Ayush-xx1bx]

Can't thank you enough, I was stuck for hours with this approach. Now I understand it completely.

[@imshivendra]

I think TechDose Sir has joined Google. Congratulations.

[@dumbcurious450]

Everyone starts with matrix directly no one says why this would work. this Man is someone who tells the exact logic behind it. Great work Mate ...

[@techdose4u]

Thanks :)

[@rutachaudhari5774]

You are way underrated for your work. Thanks for the solutions!

[@techdose4u]

Welcome :)

[@UHemanthaKumar]

Most underrated channel ! Hatsoff to you brother !

[@techdose4u]

Thanks :)

[@md_aaqil8027]

Mind-blowing Explanation
I am a fan of the way you think and solve the problem bro

[@imshivendra]

I think TechDose Sir has joined Google. Congratulations.

[@lavanyam3224]

This universe needs people like him!! Protect him :)

[@shobhitbajaj9667]

Thank you so so much
You have such a great talent ❤️ of explaining complex things like piece of cake.

[@techdose4u]

Welcome :)

[@ashishupadhyay6881]

Start watching at 10:40. Great stuff btw, thanks for this.

[@aminumado6973]

Best explanation for the unique paths problem.

[@sudhanshukumar1558]

I have already solved this problem 2 months back, hence I copied my code from there. It was bottom up approach. Good to know about the top down approach.

[@techdose4u]

I had shown bottom up in dungeon game and so I took top down this time XD

[@CostaKazistov]

Top-down DP runs slightly faster (for some reason)

[@vaishnavinatarajan3987]

Simple solution and awesome explanation ! Too helpful.

[@rahulbawa3969]

Its been 10 months and this Guy still hasn't received a medal!!!! You deserve it man! Thanks for explaining this nicely.

[@techdose4u]

Welcome :)

[@adityagoswami6881]

The best explanation,you deserve 1 Million subscriber .

[@techdose4u]

Thanks ❤️

[@imshivendra]

I think TechDose Sir has joined Google. Congratulations.

[@MrMarchador]

Very precise, clear, crisp explanation.

[@kunalsoni7681]

Really you make this problem very easy to understand 😊😇.. thanking you sir 😊

[@techdose4u]

Welcome :)

[@oqant0424]

Ur channel is a goldmine

[@ajaywadhwa3398]

What a superb explanations !! Really helped a lot.

[@techdose4u]

Thanks

[@hariprakash4237]

Sucessfully completed. Thanks for this workout

[@techdose4u]

Welcome :)

[@agileprogramming7463]

One of the easiest DP problems 😅
Also the Robot in thumbnail is 😍

[@maansi3968]

The Explanation is soo great....just came through an one line python solution.
return math.factorial(A+B-2)//(math.factorial(A-1)*math.factorial(B-1))

[@techdose4u]

Thanks

[@PriyankaSingh-pn8xv]

Amazing explanation, thanks

[@dhanashreegodase4445]

very helpful to me! thanks alot..You deserve many more likes

[@techdose4u]

Thanks

[@sathyamoorthy2888]

Iam grateful to your service sir

[@savvy9431]

This is how a coding problem should be explained.............. Everybody needs to learn from this man right here.!!!!!! Hats off🎉🎉

[@TONETHAJI]

Great explaination

[@venkateshmusuvathi8468]

Salute to ANYONE who gets this interview question and solves it within half n hr

[@imshivendra]

I think TechDose Sir has joined Google. Congratulations.

[@vibekdutta6539]

Awesome, Sir what will be the complexity of we use combinatorics for the solution, I think there is a direct solution using combinatorics

[@rogerknight8447]

By combinatorics its like
(m+n-2)C(n-1). An better SC approach though!!

[@tecocode6070]

Roger Knight how you explain this approach?

[@sulekhakumari-hs4gy]

@@tecocode6070 this problem is eqivalent to permute (m-1) down move and (n-1)right move.

[@saitejdandge2315]

Let's say, we have r X c matrix. Let's take a simple way, all down, then all right, steps=r-1(down) + c-1 (right). Ironically every other way also takes r-1+c-1 steps.
total ways is nothing but all permutations of given way (r+c-2) => (r-1+c-1)! / (r-1)! * (c-1)! => can be re written as (m+n-2)C(n-1)

[@DK-ox7ze]

Best explanation of this problem anywhere!

[@techdose4u]

Thanks :)

[@imshivendra]

I think TechDose Sir has joined Google. Congratulations.

[@DK-ox7ze]

@@imshivendra What's his real name?

[@imshivendra]

@@DK-ox7ze I don't know but I has seen on LinkedIn that he has joined Google

[@shubhammishra1225]

bohat shi samjhaya ...

[@nandk45523]

Great explanation bro appreciate it

[@ashutoshsinghrajawat6440]

Simply amazing ❤

[@ismail8973]

I literally loved this problem. Any way best explanation as always

[@imshivendra]

I think TechDose Sir has joined Google. Congratulations.

[@ALEEMKHAWAR1]

amazing solution sir

[@yatri6329]

This video is a great explanation thanks for uploading this free....

[@techdose4u]

Welcome 😊

[@Tarunkumar-si4im]

Thanks a lot sir for crystal clean explanation❣️

[@techdose4u]

Welcome :)

[@imshivendra]

I think TechDose Sir has joined Google. Congratulations.

[@275phuongvy]

great explanation. Thank you

[@techdose4u]

Welcome

[@gaunikasrivastava7851]

What is time complexity of the recursive approach?

[@imshivendra]

I think TechDose Sir has joined Google. Congratulations.

[@noobCoder26]

thanks sir for this explaination

[@techdose4u]

Welcome :)

[@acxd]

What are the Plans for July , another Challenge or Topic-wise !

[@techdose4u]

Topicwise graph algorithm.

[@shyamprakashm6325]

Could we possible to print all the unique paths? If yes how it is?

[@thegreekgoat98]

The Best!

[@amanbarnwal6668]

Awesome content as always :)
Just a simple query, at 4:07 I believe the recursive tree for node (1,0) in the right subtree is drawn wrong. Please correct me if I'm wrong.

[@imshivendra]

I think TechDose Sir has joined Google. Congratulations.

[@vijayj1997]

Can anyone explain , after breaking the dptable both robot and star are at same cell(0,0) then how the number of path will be 1?

[@bisatisrilatha7957]

what is time complexity in recursive approach and DP ?????? why?????????

[@bendesmedt9036]

Nice, you could also solve it using combinatorics: [ (rows - 1) + (columns - 1) ] ! / [ (rows - 1) ! * (columns - 1) ! ]

[@imshivendra]

I think TechDose Sir has joined Google. Congratulations.

[@CostaKazistov]

@@imshivendra I wouldn't be surprised. He is truly one of the best CS teachers here on CZcams. The guy who runs a similar channel (NeetCode) has also started working for Google last year.

[@dontgiveup5271]

Great explanation !!!! A small doubt at 13:32 I know from line 23 its used for fastIO but can I get some explanation on it. Thank You.

[@imshivendra]

The height of a conical tank is 12cm and the diameter of its base is 32cm. The cost of painting if from outside at the rate of Rs 21 per sq. cm. is

[@ShubhamMahawar_Dancer_Actor]

Its a cool solution but i have done it without recursion or Dp.I have done it by using binomial coefficient in which s.c=O(1)

[@techdose4u]

Share your code bro :)

[@SuganthanMadhav]

Excellent explanation

[@techdose4u]

Thanks :)

[@Moch117]

Nice video. Most videos start from f(m-1,n-1) i.e the bottom right but I solved it starting f(0,0) just like you
I ask myself at each step : what can i do. I can either go down or go right. Then i ask what does my f(i,j) represent. In this case, it means the number of ways I can get to the bottom right starting at i and j.
This means to calculate f(i,j), i need to know the number of ways I can get to bottom right if moved right + number of ways if I move down

[@kamele0278]

what is the point of dynamic programming if you are not using recursion ?

[@manishmundra8902]

You deserve more likes sir..

[@techdose4u]

Thanks :)

[@nileshsinha7869]

GREAT EXPLANATION SIR ❤👌

[@techdose4u]

Thanks

[@imshivendra]

I think TechDose Sir has joined Google. Congratulations.

[@snehan3341]

sir i cant understand how he says x and y are 3..? 2:50

[@prasantharavindramesh1078]

@techdose
Awesome explanation
Let's assume that the robot can move in all directions
Then how can I modify the solution?

[@techdose4u]

Assume it like a graph with 4 adjacent edges and then solve :)

[@brandoncontreras343]

THANK YOU!!!!!!

[@techdose4u]

Thanks

[@NikhilKumar-of5gb]

Code with time complexity O(1)
Code is like,
nCr:->
Where, n=rows + columns -2
r = columns -2

[@Rahul-rp5hk]

How will you calculate ncr in O(1)? I guess it ll be O(r)

[@RohitSubedi]

You can minimise the space complexity to O(M). Following is the Golang code:
func uniquePaths(m int, n int) int {
grid := make([]int, m)
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if i == 0 || j == 0 {
grid[j] = 1
} else {
grid[j] = grid[j] + grid[j-1]
}
}
}
return grid[m-1]
}

[@techdose4u]

We can optimize the space even in CPP by just maintaining a single array because we are just looking at 2 previous values :) top and left.

[@rubinluitel158]

how is this better? if you have have an array size 5, it executes 5^2 times for the videos solution but your solution also executes 25 times.

[@backtobasics6865]

code link doesn.t opens

[@Tarunkumar-si4im]

👍👍

[@techdose4u]

👍🏼

[@HARINIKUMAR-qm3jc]

I tried doing Binary Tree in timestamp 4:17 myself and found that child from node (1,0) to be (1,1) & (2,0) but in the video it is given as (1,2) could you explain me how? Thanks in advance

[@AlokDhanush-um5ol]

Tha was a mistake in the video.. It must be (2, 0) instead of (1, 2)..

[@HARINIKUMAR-qm3jc]

@@AlokDhanush-um5ol Thanks for taking time and replying :)

[@shivasaini4097]

❤

[@techdose4u]

😊

[@shailygoyal5174]

time n space complexity?

[@muhammedjack8303]

great

[@techdose4u]

Thanks

[@saitejdandge2315]

Let's say, we have r X c matrix. Let's take a simple way, all down, then all right, steps=r-1(down) + c-1 (right). Ironically every other way also takes r-1+c-1 steps.
total ways is nothing but all permutations of given way (r+c-2) => (r-1+c-1)! / (r-1)! * (c-1)! => can be re written as (m+n-2)C(n-1)

[@saurabhkanswal7954]

Not all heroes wear caps:)

[@techdose4u]

:)

[@shresthmishra9329]

Nice drawing 👌 😅

[@spetsnaz_2]

Robot is better than anything 😂🤖

[@techdose4u]

Atleast someone understands art 😭

[@ASocial093]

Did you get leetcode s t-shirt previous month? I think you got it. 😁😁

[@VrickzGamer]

Are you from NIT?

[@E__ShameemahamedS-bx2ed]

It's very similar to minimum cost path

[@techdose4u]

Yea :)

[@E__ShameemahamedS-bx2ed]

@@techdose4u Pls explain what is bottom up approach and top down approach

[@DreaMagnifier]

it's standard combinatorics problem

[@techdose4u]

👍

[@VrickzGamer]

how many are not from IIT/NIT/BITS ?

[@E__ShameemahamedS-bx2ed]

Me

[@krishnakantsharma6161]

hve anyone noticed pattern in dp table 👀

[@md_aaqil8027]

Java Solution
class Solution {
public int uniquePaths(int m, int n) {
int mat[][]=new int[n][m];
for(int i=0;i

[@_Rich_YT_]

who is feeling frustrated now ??

[@jeantharappel6633]

Why not just calculate (m+n-2)! / ( (m-1)! * (n-1)! )

[@Moch117]

Not everyone knows this formula lol

[@jeantharappel6633]

@@Moch117 it isn't a formula i used logic to covert the problem, consider m columns and n rows to get from one corner to another you need to move right (m-1) times and move down (n-1) times. The problem then becomes a permutations problem of which there are many variations. Say n is 3 and m is 4 and a down move is represented by d and a right move is represented by r. The number of permutations of rrrdd say rdrdr, rddrr etc is 5!/(3!*2!).